QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #647412 | #8354. T2 | junee | 11 | 86ms | 54592kb | C++14 | 1.4kb | 2024-10-17 13:57:51 | 2024-10-17 13:57:53 |
Judging History
answer
#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=2e6+10;
int n,m,k;
LL f[N],st[N];
LL ans[N];
struct node{
int x,v,t;
}p[N];
struct query{
int op,x;
}q[N];
void do_sub2(){
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
for(int i=1,x,y;i<=n;i++)cin>>x>>y,p[i]={x,y,x*y};
for(int i=1;i<=m;i++){
int op,x;
cin>>op>>x;
q[i]={op,x};
}
if(m==1){
do_sub2();
return 0;
}
memset(f,0,sizeof f);
memset(st,0,sizeof st);
memset(ans,-1,sizeof ans);
for(int T=1;T<=m;T++){
int op=q[T].op,x=q[T].x;
if(op==1)st[x]=1;
}
for(int i=1;i<=n;i++){
if(st[i])continue;
for(int j=k;j>=p[i].t;j--)
f[j]=max(f[j],f[j-p[i].t]+p[i].v);
}
for(int T=m;T;T--){
int op=q[T].op,x=q[T].x;
if(op==1){
for(int j=k;j>=p[x].t;j--)
f[j]=max(f[j],f[j-p[x].t]+p[x].v);
}
else if(op==2)ans[T]=f[x];
}
for(int i=1;i<=m;i++){
if(ans[i]!=-1)cout<<ans[i]<<'\n';
}
return 0;
}
/*
感觉 sub2 是好做的，直接做一个大小为 k 的背包？感觉会 T 咋办？
欸！我有一计，直接时间回溯，把最后的背包做出来，一步一步往前做，能行吗？
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 3ms
memory: 53308kb
input:
3205 5000 5000 1 1 2 1 3 1 7 1 8 1 9 1 10 1 11 1 12 2 13 1 14 2 16 1 17 2 20 3 22 1 24 1 26 2 27 1 30 1 32 2 33 1 34 1 41 1 44 2 49 2 51 1 54 2 58 2 61 2 65 2 66 1 68 2 70 1 71 2 72 2 74 8 75 3 76 5 77 1 78 7 79 5 80 5 81 1 82 2 84 1 86 6 87 6 88 3 89 9 90 5 91 1 92 2 93 3 95 7 96 2 97 2 98 8 99 8 1...
output:
81 69 32 40 42 90 32 83 44 50 91 70 53 65 82 50 68 59 86 38 67 70 79 45 50 65 88 43 37 74 29 63 73 7 53 57 75 20 44 50 47 36 73 55 30 42 78 75 47 80 66 87 36 21 73 23 88 37 68 53 57 28 46 59 56 69 28 84 26 41 64 59 35 60 5 42 35 74 63 54 87 73 83 59 39 38 45 48 89 69 62 23 82 84 31 85 56 87 81 80 66...
result:
ok 2487 lines
Test #2:
score: 11
Accepted
time: 0ms
memory: 54500kb
input:
162 5000 5000 836 4 837 5 838 5 839 5 840 4 841 4 842 4 843 4 844 4 845 4 846 5 847 4 848 4 849 5 850 4 851 5 852 5 853 4 854 5 855 4 856 5 857 4 858 4 859 4 860 5 861 5 862 4 863 4 864 4 865 5 866 5 867 4 868 5 869 4 870 4 871 5 872 4 873 4 874 5 875 4 876 4 877 5 878 5 879 4 880 4 881 5 882 5 883 ...
output:
5 0 0 3 0 5 5 0 0 4 5 0 0 0 4 3 0 5 4 0 0 0 0 0 0 4 0 0 4 0 0 5 0 0 3 3 0 0 3 0 0 4 4 0 3 3 0 4 0 0 0 4 0 0 0 0 0 0 0 0 5 0 0 0 0 0 3 0 0 0 4 0 0 5 0 0 3 5 4 0 0 3 0 4 5 4 0 0 5 4 0 0 0 0 3 0 0 0 4 5 5 5 0 4 4 4 3 5 5 5 0 3 0 3 0 4 0 4 5 3 0 0 0 3 0 5 3 0 0 0 0 0 3 0 0 4 0 0 0 0 3 4 5 3 0 4 5 3 5 0 ...
result:
ok 4838 lines
Test #3:
score: 11
Accepted
time: 3ms
memory: 52964kb
input:
3182 5000 5000 1 2597 2 404 3 409 4 220 5 604 6 248 7 48 8 145 9 97 10 356 11 111 12 158 13 192 14 309 15 168 16 251 17 234 18 68 19 223 20 111 21 235 22 152 23 188 24 48 25 75 26 9 27 34 28 153 29 58 30 18 31 153 32 76 33 150 34 52 35 121 36 37 37 7 38 79 39 96 40 101 41 8 42 66 43 61 44 77 45 83 4...
output:
404 464 0 894 701 60 758 461 758 413 758 59 708 607 551 724 59 304 97 403 290 193 194 0 242 49 49 2 363 301 146 205 363 9 97 146 335 333 335 99 410 354 243 343 97 334 343 211 211 1 236 142 9 134 194 148 60 134 168 128 94 101 0 168 76 165 101 100 61 156 95 2 111 109 152 51 9 9 110 63 20 72 44 44 71 5...
result:
ok 1818 lines
Test #4:
score: 11
Accepted
time: 5ms
memory: 53996kb
input:
3205 5000 5000 1 1 3 1 6 2 7 1 9 1 12 1 15 1 16 1 18 1 19 1 30 1 37 2 39 1 40 1 43 1 47 1 50 1 52 1 54 1 59 1 63 1 65 1 66 1 70 1 71 52 72 42 73 55 74 37 75 42 76 38 77 36 78 22 79 56 80 12 81 29 82 10 83 53 84 40 85 42 86 39 87 54 88 6 89 2 90 36 91 29 92 6 93 4 94 23 95 20 96 43 97 13 98 1 99 1 10...
output:
39 79 68 18 80 74 23 15 23 39 22 35 60 24 42 67 33 52 16 82 39 41 49 46 67 80 53 74 41 64 45 51 73 73 58 68 68 41 78 57 12 6 57 81 76 38 14 66 53 76 64 40 76 25 18 16 38 59 26 48 80 79 28 66 37 34 43 22 59 80 21 19 44 65 42 63 65 22 73 60 26 63 80 21 69 11 20 14 73 31 78 53 64 16 73 78 80 32 16 40 5...
result:
ok 4030 lines
Test #5:
score: 11
Accepted
time: 3ms
memory: 53916kb
input:
3240 5000 5000 1 4544 2 2194 3 616 4 99 5 68 6 558 7 36 8 322 9 394 10 113 11 314 12 396 13 221 14 349 15 49 16 219 17 42 18 239 19 178 20 146 21 48 22 96 23 205 24 162 25 14 26 188 27 58 28 71 29 65 30 16 31 111 32 51 33 119 34 63 35 32 36 75 37 100 38 90 39 65 40 44 41 7 42 82 43 62 44 26 45 84 46...
output:
203 819 2293 2195 224 720 99 822 252 933 784 953 224 618 252 316 423 726 358 761 218 775 421 558 219 217 220 594 203 0 68 217 594 660 252 558 316 335 771 207 204 36 296 565 744 728 7 332 285 186 332 280 216 220 239 240 626 249 558 680 678 272 636 246 562 633 275 348 87 3 68 246 288 249 87 72 69 85 7...
result:
ok 2448 lines
Test #6:
score: 11
Accepted
time: 3ms
memory: 52992kb
input:
3130 5000 5000 1 3 2 1 4 1 5 1 6 1 8 1 9 3 10 2 11 2 13 1 14 2 15 2 17 1 19 1 23 1 24 1 25 1 27 2 30 1 33 2 34 1 35 1 36 1 37 2 38 1 39 3 40 1 41 1 43 2 45 1 46 1 48 1 49 2 50 1 51 1 52 1 53 3 54 2 58 1 60 1 62 1 63 1 64 1 65 1 66 1 68 2 69 2 71 4 72 7 74 3 75 6 77 3 78 9 79 6 80 3 81 7 82 8 83 6 84...
output:
22 27 81 59 54 9 53 82 69 28 52 69 51 47 75 57 72 72 50 31 37 7 35 26 36 4 23 16 35 20 57 60 48 29 21 22 49 60 17 23 7 18 44 14 45 27 41 63 25 12 35 43 56 45 61 53 52 21 26 21 20 55 1 47 25 37 13 23 49 15 26 38 50 11 53 27 42 22 51 50 31 55 56 49 14 9 34 41 33 20 49 46 2 46 13 38 37 29 43 14 28 11 3...
result:
ok 1870 lines
Test #7:
score: 11
Accepted
time: 8ms
memory: 53792kb
input:
3220 5000 5000 1 1716 2 2046 3 1005 4 308 5 629 6 117 7 344 8 562 9 27 10 244 11 177 12 141 13 330 14 87 15 306 16 219 17 211 18 145 19 254 20 58 21 215 22 37 23 135 24 194 25 38 26 12 27 175 28 97 29 39 30 89 31 72 32 64 33 7 34 62 35 30 36 130 37 132 38 12 39 21 40 26 41 68 42 110 43 21 44 108 45 ...
output:
311 2184 2051 117 1860 1743 115 1762 1755 1837 50 1831 1767 1921 1780 2061 1837 28 1719 47 2063 1767 2099 2073 87 115 1718 3 115 1719 1842 1756 1723 40 1756 1758 1843 2100 27 88 2064 1803 28 1781 1842 1716 27 117 1718 1781 1 2345 65 48 28 3 1843 34 2346 1868 1743 88 1803 34 2063 2345 1810 2060 1746 ...
result:
ok 3964 lines
Test #8:
score: 11
Accepted
time: 3ms
memory: 54592kb
input:
3157 5000 5000 2 1 4 1 5 1 8 2 10 1 16 1 18 1 22 1 24 1 25 1 26 2 29 2 34 1 36 1 40 1 42 2 43 1 45 2 46 1 47 1 49 3 51 1 55 1 57 1 67 3 68 1 70 1 71 12 72 18 73 15 74 49 75 15 76 12 77 49 78 9 79 5 80 46 81 38 82 4 83 46 84 58 85 26 86 14 87 13 88 39 89 5 90 51 91 24 92 44 93 51 94 19 95 10 96 16 97...
output:
62 82 36 41 48 71 71 83 78 64 16 80 27 72 72 37 0 30 61 35 70 5 19 56 48 19 49 57 40 24 76 45 69 48 45 42 25 63 13 42 38 45 54 42 45 75 6 34 45 58 5 78 64 56 17 74 70 72 41 69 33 70 64 33 26 77 27 19 36 37 5 29 66 38 20 54 23 34 33 55 18 20 52 67 25 5 8 27 22 41 29 41 72 18 43 21 29 5 49 11 39 60 49...
result:
ok 2523 lines
Test #9:
score: 11
Accepted
time: 3ms
memory: 53796kb
input:
3233 5000 5000 1 4147 2 1080 3 1621 4 237 5 939 6 694 7 374 8 42 9 501 10 222 12 195 13 208 14 75 15 298 16 141 17 213 18 232 19 196 20 65 21 91 22 4 23 48 24 200 25 53 26 139 27 80 28 109 29 19 30 132 31 123 32 43 33 16 34 129 35 138 36 85 37 112 38 44 39 44 40 42 41 103 42 76 43 43 44 19 45 65 46 ...
output:
701 316 247 463 703 261 104 26 240 698 164 240 703 193 76 53 7 52 53 71 28 8 20 9 194 200 26 217 198 151 162 163 143 167 163 152 113 58 7 87 167 47 104 143 58 200 163 201 1 71 145 24 57 38 38 41 66 72 24 145 63 147 47 5 136 78 61 5 71 29 72 19 3 24 66 78 84 3 84 50 70 74 0 68 82 3 90 17 9 87 2 5 17 ...
result:
ok 1767 lines
Test #10:
score: 11
Accepted
time: 0ms
memory: 53564kb
input:
411 5000 5000 1253 3 1254 3 1255 3 1256 3 1257 3 1258 3 1259 3 1260 3 1261 3 1262 3 1263 3 1264 3 1265 3 1266 3 1267 3 1268 3 1269 3 1270 3 1271 3 1272 3 1273 3 1274 3 1275 3 1276 3 1277 3 1278 3 1279 3 1280 3 1281 3 1282 3 1283 3 1284 3 1285 3 1286 3 1287 3 1288 3 1289 3 1290 3 1291 3 1292 3 1293 3...
output:
3 2 2 3 0 0 3 0 0 0 3 0 3 0 0 3 3 2 2 0 2 0 2 0 3 0 3 2 3 0 2 3 0 0 2 0 0 0 0 2 3 3 0 0 0 2 3 0 0 0 0 0 0 2 0 0 3 0 0 0 0 2 0 0 0 0 3 2 3 0 0 0 2 2 0 3 0 0 0 2 3 2 0 2 2 3 3 3 0 2 0 3 0 0 2 0 0 3 0 3 0 3 2 3 0 0 0 3 0 2 2 0 0 3 2 0 0 0 3 2 0 3 2 0 0 3 2 3 0 2 0 0 0 2 3 3 0 0 0 2 0 0 0 0 0 3 0 3 2 3 ...
result:
ok 4589 lines
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 86ms
memory: 20104kb
input:
1277351 1 2000000 2 2 5 1 7 3 8 4 10 1 12 1 15 2 16 1 18 1 22 1 25 1 28 3 29 1 32 1 35 1 36 1 38 2 40 1 41 2 42 1 43 2 44 2 45 1 48 1 49 1 50 2 54 2 55 2 56 1 58 2 59 2 60 2 62 1 66 1 68 3 69 1 70 3 72 2 76 1 78 1 79 2 81 2 82 3 84 2 85 1 86 2 89 1 90 2 91 2 92 1 93 1 96 3 98 3 99 2 100 3 101 1 102 ...
output:
result:
wrong answer 1st lines differ - expected: '1771', found: ''
Subtask #3:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
input:
5000 5000 2000000 1 1 2 1 3 1 4 1 6 1 7 1 8 1 9 1 10 1 11 1 14 1 15 3 17 2 18 2 21 1 22 1 24 1 25 3 27 1 28 2 29 1 30 1 31 1 32 1 33 1 34 1 35 1 37 1 38 1 39 1 40 2 41 2 43 1 45 1 47 1 49 1 50 1 51 1 54 1 55 1 56 1 61 1 62 2 64 1 65 1 67 2 68 2 70 2 72 2 74 1 76 3 79 2 82 4 83 2 84 1 88 1 91 1 92 1 ...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #31:
score: 0
Time Limit Exceeded
input:
191299 5000 300000 1 1 5 1 6 2 7 1 8 1 10 1 11 2 12 2 17 1 18 1 19 1 20 1 21 1 22 2 25 1 28 1 29 2 30 1 31 2 34 1 36 1 37 1 38 1 40 1 42 1 43 1 44 1 45 1 47 2 48 1 51 1 53 3 54 2 56 2 58 2 59 2 61 2 63 4 64 2 67 1 68 2 69 2 70 1 72 1 76 1 77 1 78 1 80 2 83 1 84 1 87 1 88 1 89 1 91 2 93 1 95 1 96 1 9...
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #41:
score: 0
Time Limit Exceeded
input:
1278949 5000 2000000 4 1 9 1 12 1 13 1 15 2 20 1 21 2 26 1 36 1 39 2 43 1 46 2 59 1 64 1 66 1 71 1 73 1 75 1 78 2 83 1 87 1 89 1 92 1 97 1 103 1 104 1 108 1 111 1 113 1 114 1 117 2 118 1 130 1 137 1 140 1 151 1 152 1 155 1 158 2 163 1 164 1 165 1 168 1 172 1 173 1 183 1 185 1 186 1 192 1 208 1 210 2...