fork(2) download
  1. #include<stdio.h>
  2. #include<map>
  3. #include<string.h>
  4.  
  5.  
  6. const int LIMIT=2000;
  7. int xs[LIMIT+1];
  8. std::map<int,int> ts;
  9. int dp[LIMIT+1][LIMIT+1];
  10.  
  11. int main(){
  12. int s,n,m;
  13. scanf("%d %d %d",&s,&n,&m);
  14. for(int i=0;i<s;i++){
  15. scanf("%d",&xs[i]);
  16. }
  17. int t,p;
  18. for(int i=0;i<n;i++){
  19. scanf("%d %d",&t,&p);
  20. ts[t-xs[p-1]]++;
  21. }
  22. std::map<int,int> temp;
  23. std::map<int,int>::iterator it;
  24. int minT=(*(ts.begin())).first;
  25. for(it=ts.begin();it!=ts.end();it++){
  26. temp[(*it).first-minT]=(*it).second;
  27. }
  28. ts.clear();
  29. ts.insert(temp.begin(),temp.end());
  30. std::map<int,int>::reverse_iterator rIt;
  31.  
  32.  
  33. rIt=ts.rbegin();
  34. int oldF=(*rIt).first;
  35. rIt++;
  36. memset(dp,-1,sizeof(dp));
  37. dp[1][1]=0;
  38. int size=1;
  39. int pos=2;
  40. int sums[LIMIT+1]={0};
  41. for(;rIt!=ts.rend();rIt++){
  42. size++;
  43. if(m<size)size=m;
  44.  
  45. int f=(*rIt).first;
  46. int s=(*rIt).second;
  47. //printf("<%d %d>",f,s);
  48.  
  49. for(int i=1;i<=size;i++){
  50. if(dp[pos-1][i]!=-1){
  51. sums[i]+=oldF-f;
  52. dp[pos][i]=dp[pos-1][i]+sums[i]*s;
  53. }
  54. }
  55. for(int i=2;i<=size;i++){
  56. if(dp[pos][i]==-1){
  57. sums[i]=0;
  58. dp[pos][i]=dp[pos-1][i-1];
  59. }else{
  60. if(dp[pos][i]>=dp[pos-1][i-1]){
  61. sums[i]=0;
  62. dp[pos][i]=dp[pos-1][i-1];
  63. }
  64. }
  65. }
  66. //printf("(%d %d)",size,dp[pos][size]);
  67. //for(int i=0;i<4;i++){
  68. // for(int j=0;j<4;j++){
  69. // printf("%d\t",dp[i+1][j+1]);
  70. // }
  71. // printf("\n");
  72. //}
  73. //printf("\n");
  74. pos++;
  75. oldF=f;
  76. }
  77. printf("%d\n",dp[pos-1][size]);
  78. }
Success #stdin #stdout 0.02s 18888KB
stdin
1530 500 197
1 6 38 55 65 79 80 85 86 89 99 101 105 115 117 119 125 127 134 143 144 147 156 164 168 169 173 181 184 190 202 205 206 211 215 222 228 231 240 248 258 265 285 286 294 301 302 307 309 311 317 343 353 355 356 358 363 364 371 384 388 391 395 401 402 405 407 413 414 429 435 437 438 444 451 454 458 471 479 480 481 482 502 506 520 538 541 543 545 549 569 571 585 599 628 638 643 644 647 651 654 684 687 689 696 710 711 716 718 722 728 737 740 742 748 749 750 751 753 757 776 780 786 787 788 789 794 797 809 814 816 821 831 839 843 866 875 889 892 900 902 905 915 920 929 933 934 961 962 969 970 974 976 978 983 986 996 1001 1026 1037 1041 1053 1062 1064 1073 1077 1083 1088 1092 1093 1105 1110 1113 1114 1118 1120 1121 1138 1149 1159 1161 1163 1172 1178 1181 1190 1197 1199 1206 1207 1218 1223 1231 1237 1243 1244 1248 1253 1256 1258 1259 1286 1288 1301 1304 1308 1313 1316 1319 1322 1324 1338 1341 1357 1364 1375 1376 1381 1390 1395 1402 1412 1415 1423 1425 1430 1446 1450 1456 1463 1466 1477 1484 1490 1501 1503 1510 1523 1535 1547 1551 1569 1574 1595 1600 1603 1608 1621 1636 1637 1638 1639 1644 1646 1655 1661 1668 1670 1679 1703 1704 1709 1712 1713 1714 1715 1718 1720 1722 1724 1738 1739 1754 1758 1759 1761 1762 1772 1776 1780 1793 1794 1810 1814 1828 1835 1837 1841 1847 1868 1873 1876 1887 1897 1903 1908 1921 1922 1924 1938 1947 1971 1972 1978 1981 1984 1985 1992 1998 2018 2021 2030 2031 2043 2046 2063 2066 2070 2085 2086 2095 2098 2102 2112 2121 2123 2129 2130 2138 2139 2141 2142 2148 2155 2161 2179 2195 2198 2205 2216 2218 2224 2227 2232 2248 2258 2263 2266 2271 2272 2275 2276 2278 2285 2286 2293 2295 2298 2305 2309 2313 2314 2334 2336 2349 2352 2357 2359 2361 2363 2375 2380 2381 2382 2388 2389 2390 2409 2411 2418 2426 2428 2432 2439 2440 2447 2464 2465 2468 2478 2485 2490 2500 2506 2525 2541 2552 2583 2594 2595 2614 2618 2624 2627 2637 2655 2656 2660 2666 2667 2670 2674 2677 2679 2700 2728 2735 2737 2740 2773 2780 2787 2788 2791 2795 2803 2823 2831 2833 2847 2858 2864 2868 2876 2878 2879 2884 2888 2895 2897 2899 2908 2924 2928 2929 2934 2938 2956 2960 2961 2963 2965 2972 2976 2978 2992 2997 3006 3010 3011 3015 3018 3031 3041 3043 3044 3055 3069 3072 3073 3077 3087 3090 3091 3113 3116 3120 3126 3137 3162 3164 3166 3175 3179 3186 3188 3193 3204 3214 3216 3217 3221 3234 3236 3238 3243 3257 3263 3264 3267 3277 3283 3286 3287 3302 3308 3320 3326 3328 3345 3346 3347 3360 3373 3382 3383 3387 3388 3433 3462 3468 3478 3489 3492 3494 3498 3514 3516 3524 3525 3542 3548 3550 3554 3560 3564 3579 3581 3586 3592 3598 3607 3619 3631 3636 3639 3643 3645 3653 3657 3673 3683 3685 3691 3694 3703 3706 3707 3709 3711 3725 3735 3745 3755 3756 3773 3774 3776 3784 3786 3789 3793 3794 3796 3801 3808 3810 3823 3829 3839 3844 3855 3866 3883 3888 3904 3905 3906 3912 3914 3917 3922 3926 3938 3943 3944 3946 3949 3951 3956 3969 3970 3972 3974 3978 3989 3999 4015 4034 4037 4043 4046 4053 4056 4059 4069 4075 4078 4079 4084 4089 4105 4108 4109 4114 4118 4120 4128 4132 4137 4139 4147 4150 4155 4172 4175 4188 4202 4208 4215 4216 4225 4248 4251 4253 4256 4269 4273 4278 4279 4294 4298 4300 4309 4314 4315 4320 4334 4344 4345 4352 4360 4361 4367 4379 4386 4393 4394 4395 4399 4409 4410 4438 4455 4458 4462 4482 4489 4494 4501 4504 4513 4517 4531 4532 4544 4545 4546 4557 4561 4567 4582 4593 4596 4600 4620 4627 4634 4652 4655 4668 4672 4674 4686 4688 4689 4695 4708 4709 4733 4739 4741 4745 4749 4750 4752 4757 4767 4769 4773 4775 4778 4781 4783 4791 4801 4802 4803 4809 4811 4823 4828 4829 4834 4839 4840 4849 4851 4858 4873 4881 4884 4893 4912 4925 4927 4928 4951 4955 4962 4969 4970 4987 4993 5012 5018 5021 5027 5029 5041 5042 5044 5057 5063 5067 5073 5077 5080 5084 5091 5093 5107 5119 5126 5137 5153 5155 5159 5164 5177 5178 5180 5184 5198 5202 5203 5224 5226 5229 5231 5237 5248 5253 5257 5281 5283 5295 5304 5309 5318 5340 5342 5344 5345 5350 5355 5358 5369 5379 5381 5396 5398 5399 5403 5406 5408 5412 5420 5421 5427 5430 5431 5436 5442 5445 5451 5462 5471 5473 5493 5500 5504 5505 5507 5508 5523 5529 5536 5551 5552 5555 5557 5558 5560 5568 5570 5573 5578 5597 5598 5600 5607 5617 5623 5629 5635 5636 5654 5657 5666 5667 5668 5674 5675 5679 5683 5687 5689 5691 5694 5697 5701 5708 5717 5721 5725 5738 5740 5741 5750 5760 5761 5775 5778 5797 5803 5807 5829 5837 5838 5841 5844 5846 5851 5856 5858 5867 5870 5872 5876 5877 5883 5914 5915 5924 5944 5950 5953 5956 5957 5958 5963 5966 5973 5976 5989 5990 5991 5993 6009 6010 6020 6029 6030 6044 6049 6051 6057 6061 6064 6068 6073 6076 6085 6117 6129 6141 6153 6156 6159 6168 6195 6196 6202 6210 6222 6223 6226 6240 6243 6246 6264 6266 6270 6271 6290 6293 6294 6297 6305 6321 6326 6334 6338 6351 6361 6363 6376 6378 6379 6385 6386 6387 6392 6400 6404 6405 6408 6411 6417 6420 6422 6424 6443 6451 6457 6462 6464 6480 6485 6491 6498 6502 6507 6508 6518 6521 6524 6530 6544 6551 6553 6574 6578 6584 6585 6601 6602 6603 6607 6614 6621 6624 6629 6632 6662 6664 6671 6672 6678 6680 6693 6699 6703 6708 6720 6728 6733 6735 6748 6749 6752 6753 6764 6767 6769 6772 6780 6781 6791 6794 6802 6813 6815 6816 6818 6824 6830 6833 6843 6845 6850 6852 6857 6862 6874 6890 6914 6916 6923 6926 6933 6934 6938 6944 6954 6957 6971 6982 6988 6989 6999 7021 7040 7050 7054 7055 7058 7062 7068 7074 7078 7082 7083 7091 7092 7093 7094 7103 7105 7106 7107 7120 7121 7127 7138 7144 7147 7174 7177 7178 7183 7192 7208 7212 7215 7224 7229 7234 7235 7239 7245 7256 7259 7260 7284 7287 7291 7292 7293 7294 7296 7298 7300 7309 7317 7321 7329 7347 7352 7362 7371 7389 7401 7404 7408 7409 7410 7415 7416 7434 7435 7441 7443 7444 7451 7457 7467 7468 7475 7476 7490 7494 7500 7506 7511 7512 7520 7537 7550 7555 7561 7562 7571 7573 7576 7582 7587 7588 7589 7596 7608 7609 7611 7627 7629 7630 7634 7635 7644 7652 7660 7661 7664 7673 7674 7681 7683 7684 7686 7688 7701 7703 7707 7709 7710 7719 7727 7731 7733 7735 7739 7750 7761 7763 7767 7773 7776 7777 7781 7787 7790 7796 7798 7806 7809 7816 7817 7819 7820 7821 7827 7828 7838 7843 7874 7875 7880 7885 7901 7902 7903 7908 7912 7918 7919 7933 7940 7941 7946 7949 7953 7955 7957 7966 7977 7982 8009 8013 8021 8035 8036 8039 8045 8046 8052 8058 8060 8064 8066 8068 8081 8116 8121 8135 8136 8142 8156 8162 8163 8170 8172 8177 8184 8188 8194 8198 8207 8209 8215 8246 8247 8249 8253 8257 8261 8267 8276 8288 8293 8294 8299 8316 8328 8330 8350 8352 8353 8364 8381 8387 8391 8393 8394 8407 8408 8423 8425 8432 8434 8453 8472 8473 8478 8482 8491 8504 8508 8511 8513 8515 8520 8531 8533 8534 8542 8553 8595 8596 8598 8599 8604 8614 8617 8634 8647 8660 8673 8678 8679 8685 8686 8690 8693 8694 8695 8704 8705 8707 8708 8710 8713 8714 8716 8724 8727 8729 8749 8762 8769 8775 8778 8784 8792 8805 8808 8811 8814 8818 8820 8827 8832 8834 8866 8867 8872 8877 8889 8890 8896 8902 8913 8920 8922 8929 8946 8951 8956 8957 8962 8964 8966 8971 8976 8985 9002 9006 9009 9018 9060 9061 9072 9074 9085 9092 9106 9112 9114 9117 9122 9127 9129 9131 9138 9140 9141 9142 9144 9150 9152 9162 9164 9172 9185 9186 9198 9209 9222 9225 9228 9239 9246 9258 9259 9260 9261 9271 9273 9278 9283 9292 9311 9318 9343 9346 9347 9348 9366 9367 9372 9392 9409 9420 9425 9426 9429 9430 9433 9446 9450 9451 9463 9473 9481 9488 9497 9503 9518 9520 9529 9536 9537 9547 9576 9579 9583 9591 9594 9599 9605 9617 9622 9623 9628 9637 9639 9641 9642 9644 9645 9661 9662 9664 9697 9710 9713 9715 9718 9720 9725 9737 9742 9754 9772 9773 9786 9802 9834 9836 9840 9858 9871 9881 9883 9891 9898 9903 9905 9908 9913 9926 9930 9935 9947 9952 9967 9974 9985 9991 9996
1496 1469
4541 1066
3232 513
6478 161
795 31
9123 1202
488 833
4402 1020
9626 297
6994 269
4839 994
2416 656
1716 485
9441 451
8460 222
9554 65
588 693
8198 622
3808 1137
9792 191
5028 677
9874 691
995 92
9247 1327
4272 10
4495 968
9604 108
6850 86
7973 1134
4207 1524
5199 383
9801 1275
6752 619
3940 600
1427 896
2301 324
4413 130
5911 999
8403 991
1376 645
1123 1372
1965 681
697 599
76 166
7443 837
9302 1491
3481 580
3309 566
4202 1275
2927 897
7418 918
8648 228
9033 391
621 1172
5436 106
7936 1111
1695 1082
9202 1156
7044 227
2389 513
76 164
9108 1451
7779 874
3052 1470
8495 1422
5336 1083
7648 1392
1725 414
4389 375
8261 397
7633 533
5620 1010
7398 752
573 601
5357 12
7530 284
3598 1113
3435 960
1225 1199
8845 186
8673 1325
9956 343
4039 1156
3654 1401
6563 200
7561 221
6941 1504
7582 291
2784 967
704 226
7165 1235
5328 877
2697 1160
3141 75
5303 378
9109 1525
4897 625
2268 658
8279 780
3739 1278
1029 435
3785 198
4227 61
4593 928
9394 1050
5098 1014
4130 1098
5059 657
9231 517
1902 1107
8976 956
8227 360
5867 980
2057 1130
4187 1504
3225 354
7918 407
5051 609
9350 815
6591 1470
6075 513
7530 1333
7043 811
2770 979
6833 15
9028 1093
7366 816
271 762
1372 1385
1634 912
2612 1188
2392 629
4102 1393
1000 21
99 1298
8405 82
9807 1362
10000 341
6193 1247
7286 1289
7977 1338
7249 941
8634 53
7079 1529
5823 565
6441 34
318 268
6801 758
191 80
3364 55
9702 951
3271 312
8801 130
3094 567
9483 205
4472 301
8228 579
8725 1352
3952 111
1117 404
7785 958
5772 300
3221 114
1672 366
6871 950
9506 1156
4388 383
7619 614
5655 757
2466 228
9513 939
7659 1185
9200 459
5855 231
8531 329
6750 262
7220 1289
4695 490
8306 72
7398 111
4738 292
4230 1110
9491 1306
6455 1402
8917 241
4516 1161
800 1248
6548 485
3554 1198
7089 1488
414 908
2713 191
3349 1457
6954 70
5128 1055
9308 516
1053 629
3209 1398
3942 301
7555 551
9280 889
8392 251
6925 745
1066 201
7307 123
6732 841
4945 1362
7706 24
4771 325
8884 776
3566 909
9154 630
300 475
8480 1383
9290 113
4832 78
2975 1065
2651 289
1886 655
8361 28
6724 381
3802 495
7293 1070
3174 346
7965 356
2790 618
4117 1333
4666 940
1650 469
7415 1091
6672 1368
3459 745
4540 1325
6492 1153
8644 366
3578 754
2790 1493
7139 158
225 779
6500 648
3796 1070
363 1216
4189 952
8033 1397
6527 652
516 747
4463 615
6003 711
7106 645
2223 720
2465 929
9495 1484
5217 679
5714 1270
9578 1252
2163 739
5560 102
7639 1417
8567 1076
7668 1395
554 485
7106 251
549 1291
3943 847
4215 1273
9369 447
880 211
9796 355
9316 108
7850 1340
5126 176
5496 49
570 699
4402 1053
5986 950
808 1357
3933 209
9137 1515
8419 543
7383 192
9487 127
7043 806
8133 1234
6355 1449
9483 1473
6585 719
3062 1139
6203 53
8516 650
597 561
7999 1223
8314 1456
6112 1238
4104 413
8038 706
1646 640
4423 8
598 110
6597 1461
7856 973
354 1120
2780 376
9250 590
9378 780
2306 1321
1168 916
8687 204
997 1152
6000 253
2854 1234
9023 202
4120 860
1823 1265
4718 144
4973 1399
1824 552
7782 817
1851 1412
3606 6
2859 1318
7342 153
4726 692
1222 402
6270 710
3196 1079
4564 1491
652 684
5739 987
2409 632
5414 1039
6459 125
8239 928
8305 1364
9963 540
366 889
3312 656
1706 721
8987 718
9696 1211
9206 369
3098 96
6807 1021
1152 1251
6118 618
110 742
1031 272
4197 578
2565 1226
8566 722
1631 812
6018 984
943 1003
3760 891
851 377
7257 725
3347 964
2270 35
1001 945
659 362
9344 444
6268 1072
5228 549
8339 1256
67 307
5271 768
6613 218
8694 636
2152 204
7567 1345
8157 855
4583 1051
6335 793
647 1513
6851 272
5825 639
3773 379
6360 43
7672 1281
287 490
3947 618
9919 1214
2227 628
9827 1424
793 678
523 1281
1526 929
8410 1457
5720 323
7669 627
1268 726
267 319
1640 929
5524 771
6681 87
2171 767
7017 886
9650 877
8953 1111
4291 277
6152 41
7095 1431
3415 1240
9346 620
590 1353
5729 516
8783 1305
8837 1503
6744 46
2598 281
905 341
6931 885
2479 211
4765 396
7117 245
2913 349
4567 688
8958 27
7409 209
6046 614
3217 885
2883 1426
4902 1458
2887 459
8110 1265
9262 486
3168 816
4912 407
3464 72
6644 1464
5148 907
4583 1187
6255 416
9882 286
325 1109
8343 995
7166 989
4744 414
4149 103
3128 335
6212 1368
860 1487
1349 553
2927 872
8942 138
725 1259
6583 350
9941 678
2110 342
1203 1268
6738 210
5951 750
5091 1152
7654 547
3733 78
9236 1469
4265 946
3753 49
5424 1509
6320 551
2346 900
7243 1228
6231 726
8111 1530
7512 1528
3421 1029
2054 1497
2353 166
9922 746
5128 139
49 403
2009 696
750 863
2566 248
7626 423
7559 893
5905 898
3836 896
5403 820
4665 226
941 391
877 736
5922 479
7620 1492
8377 1443
7544 1319
9045 472
7781 1437
1040 952
9333 1359
723 1411
9026 512
991 1509
919 10
4698 1349
6531 511
3287 770
7928 1455
6022 1463
5866 491
6016 386
stdout
6850