ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 22.12.2018 12:06:56

ამოცანა: CST-ის ოლიმპიადა

მომხმარებელი: lukamosiashvili

ვერდიქტი: ნაწილობრივი ამოხსნა

შეფასება: 63.6 ქულა







#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,dp[101][520009],m,n=-999999999999LL,pas;
pair <long long, long long> p[109];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(b=1; b<=a; b++) cin>>p[b].first>>p[b].second;
	m=110002;
	for(b=1; b<=a; b++){
		for(c=-110002; c<=110002; c++){
			dp[b][c+m]=n;
		}
	}
	dp[1][p[1].first+m]=p[1].second;
	for(b=2; b<=a; b++){
		for(c=-1000*b; c<=1000*b; c++){
		    if(dp[b][c+m]<dp[b-1][c+m]){
					dp[b][c+m]=dp[b-1][c+m];
				}
			if(dp[b-1][c-p[b].first+m]!=n){
				if(dp[b][c+m]<dp[b-1][c-p[b].first+m]+p[b].second){
					dp[b][c+m]=dp[b-1][c-p[b].first+m]+p[b].second;
				}
			}
		}
	}
	for(b=1; b<=a; b++){
		for(c=0; c<=1000*b; c++){
			if(dp[b][c+m]>=0&&pas<dp[b][c+m]+c){
				pas=dp[b][c+m]+c;
			}
		}
	}
	cout<<pas;
	return 0;
}

ტესტები

შემავალი მონაცემები
5
-5 7
8 -6
6 -3
2 1
-8 -5
გამომავალი მონაცემები
8
თქვენი პასუხი
8
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
-782 790
20 -19
-867 867
-886 892
74 -83
-273 269
-662 664
523 -516
557 -553
-946 943
-323 329
-402 393
-833 840
644 -645
831 -833
239 -240
233 -226
-546 556
977 -985
858 -864
-919 920
346 -348
-866 869
122 -116
-963 962
896 -905
-83 93
227 -233
-276 2...
გამომავალი მონაცემები
221
თქვენი პასუხი
221
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10
-1 -49
6 -13
-35 -16
-50 -47
-68 -52
19 -92
17 -18
71 -96
-48 47
-91 5
გამომავალი მონაცემები
0
თქვენი პასუხი
0
ჩეკერის პასუხი
YES
შემავალი მონაცემები
20
312 -311
-316 317
-105 106
430 -429
-935 936
60 -59
656 -655
-287 288
505 -504
609 -608
818 -817
877 -876
78 -77
-564 565
-950 951
-443 444
650 -649
574 -573
-609 610
-75 76
გამომავალი მონაცემები
17
თქვენი პასუხი
17
ჩეკერის პასუხი
YES
შემავალი მონაცემები
20
-179 -232
574 -308
-914 -309
358 -672
-49 407
162 747
92 498
724 -773
175 713
954 -516
-477 12
987 453
705 703
96 -920
13 -770
-562 391
-445 569
-918 -358
-741 441
-30 -233
გამომავალი მონაცემები
6421
თქვენი პასუხი
6010
ჩეკერის პასუხი
NO
შემავალი მონაცემები
50
-519 -81
-368 -110
603 780
-823 946
115 -219
-544 821
157 910
204 80
-617 -361
625 47
-913 -316
-146 -669
393 -662
273 -43
18 -635
-67 499
-159 122
946 -556
-99 -877
-611 573
-539 -154
394 619
-688 -846
-745 -748
-206 881
-144 -119
-436 710
-231 514
606...
გამომავალი მონაცემები
11353
თქვენი პასუხი
10753
ჩეკერის პასუხი
NO
შემავალი მონაცემები
100
694 969
-208 -676
-259 156
-682 936
-84 749
-488 172
383 -99
-610 -11
-953 376
-272 203
-55 191
-578 125
-160 -505
-405 -375
237 -5
804 -513
-37 -848
-189 262
308 -313
-246 -777
-565 -176
-47 819
725 343
-636 329
-724 -350
-469 221
398 -490
903 -763
-4...
გამომავალი მონაცემები
33169
თქვენი პასუხი
33169
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10
-67 36
-92 -71
-81 -12
89 16
-38 94
47 -27
69 20
4 19
60 89
19 9
გამომავალი მონაცემები
470
თქვენი პასუხი
439
ჩეკერის პასუხი
NO
შემავალი მონაცემები
15
312 -311
-316 317
-105 106
430 -429
-935 936
60 -59
656 -655
-287 288
505 -504
609 -608
818 -817
877 -876
78 -77
-564 565
-950 951
გამომავალი მონაცემები
12
თქვენი პასუხი
12
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50
5 -69
-52 78
-33 54
93 -62
42 -22
-85 41
-39 20
22 -8
43 -97
21 -42
-28 69
-61 29
-59 47
7 -36
-78 100
-55 39
56 -33
-43 41
57 -20
83 -41
-71 85
48 -6
-4 89
96 -72
38 -78
-78 53
-9 12
-97 91
-100 59
-44 90
10 -42
-90 71
-67 34
51 -64
-63 42
-21 63
35 -3...
გამომავალი მონაცემები
674
თქვენი პასუხი
610
ჩეკერის პასუხი
NO
შემავალი მონაცემები
100
52 -51
459 -458
559 -558
390 -389
977 -976
230 -229
-267 268
-531 532
123 -122
195 -194
-15 16
-552 553
-268 269
-826 827
942 -941
-436 437
903 -902
302 -301
-74 75
70 -69
-952 953
-677 678
276 -275
-846 847
69 -68
957 -956
-872 873
556 -555
-682 683
-...
გამომავალი მონაცემები
99
თქვენი პასუხი
99
ჩეკერის პასუხი
YES