QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #365029 | #2734. Professional Network | D_F_S | 4 | 2ms | 9664kb | C++14 | 924b | 2024-03-24 18:21:13 | 2024-03-24 18:21:14 |
answer
#include<bits/stdc++.h>
#define inl inline
using namespace std;
const int N=1005,IB=1<<21; char IN[IB],*IS=IN+IB,*IT=IS;
#define getchar() (IS==IT&&(IT=IN+fread(IS=IN,1,IB,stdin)),IS==IT?EOF:*IS++)
struct A {int c,v; }a[N];
int n,an,b[N],f[N][N];
inl int Read()
{
int s=0; char c; while(!isdigit(c=getchar()));
for(;isdigit(c);c=getchar()) s=s*10+c-'0'; return s;
}
int main()
{
n=Read(); for(int i=1;i<=n;++i) a[i]={Read(),Read()}, ++b[a[i].c];
sort(a+1,a+n+1,[](A x,A y){return x.c==y.c?x.v>y.v:x.c<y.c; });
memset(f,63,sizeof(f)); for(int i=1;i<=n;++i) b[i]+=b[i-1];
an=f[0][0]; f[n+1][0]=0; for(int i=n;i;--i)
{
for(int j=a[i].c-b[a[i].c-1];j<=n-i;++j) f[i][j]=f[i+1][j];
for(int j=0;j<=n-i;++j) f[i][j+1]=min(f[i][j+1],f[i+1][j]+a[i].v);
for(int j=1;j<=n;++j) if(f[i][j-1]!=an) assert(f[i][j-1]<=f[i][j]);
}
for(int i=0;i<=n;++i) an=min(an,f[1][i]);
printf("%d\n",an); return 0;
}
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
200000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0...
output:
result:
Subtask #2:
score: 4
Accepted
Test #11:
score: 4
Accepted
time: 2ms
memory: 9404kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 9068kb
input:
10 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000 10 10000
output:
100000
result:
ok single line: '100000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 8628kb
input:
10 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 7768kb
input:
10 10 219 9 728 8 425 8 380 7 512 7 617 8 434 9 789 8 74 7 100
output:
2360
result:
ok single line: '2360'
Test #15:
score: 0
Accepted
time: 2ms
memory: 8656kb
input:
10 2 7163 7 7183 9 8179 9 6271 7 6425 7 1502 7 1115 5 6916 3 184 8 6840
output:
15313
result:
ok single line: '15313'
Test #16:
score: 0
Accepted
time: 2ms
memory: 8564kb
input:
10 7 3593 8 2206 9 290 5 1836 10 5899 8 2166 7 6378 10 3962 8 2120 9 684
output:
15121
result:
ok single line: '15121'
Test #17:
score: 0
Accepted
time: 2ms
memory: 8104kb
input:
10 3 3235 10 325 9 806 8 2534 10 3271 10 641 8 192 9 43 8 815 9 2397
output:
6093
result:
ok single line: '6093'
Test #18:
score: 0
Accepted
time: 0ms
memory: 7836kb
input:
10 7 387 7 1461 9 1180 0 1809 9 616 9 605 1 300 7 857 0 620 10 1018
output:
2626
result:
ok single line: '2626'
Test #19:
score: 0
Accepted
time: 0ms
memory: 8752kb
input:
10 6 54 10 4496 6 1946 4 4677 5 3791 8 4101 6 4720 2 3859 10 4381 6 3219
output:
8931
result:
ok single line: '8931'
Test #20:
score: 0
Accepted
time: 2ms
memory: 8336kb
input:
10 7 275 2 2001 8 5315 1 3938 10 530 3 3584 10 4559 7 1934 4 52 9 5043
output:
5364
result:
ok single line: '5364'
Test #21:
score: 0
Accepted
time: 0ms
memory: 8708kb
input:
10 9 1500 0 635 1 1825 4 1934 3 2015 9 332 10 1956 2 1782 9 1283 2 1238
output:
3571
result:
ok single line: '3571'
Test #22:
score: 0
Accepted
time: 2ms
memory: 9336kb
input:
5 4 4561 5 3797 4 6708 5 982 1 2333
output:
9340
result:
ok single line: '9340'
Test #23:
score: 0
Accepted
time: 2ms
memory: 8372kb
input:
8 8 1687 2 3319 4 1742 7 2319 4 3378 2 4107 4 316 0 2405
output:
1687
result:
ok single line: '1687'
Test #24:
score: 0
Accepted
time: 2ms
memory: 7824kb
input:
3 0 762 0 1464 0 316
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 2ms
memory: 8588kb
input:
1 1 1686
output:
1686
result:
ok single line: '1686'
Test #26:
score: 0
Accepted
time: 2ms
memory: 8796kb
input:
8 2 2361 2 3762 6 2726 8 6136 1 2163 0 5565 2 4962 3 400
output:
6136
result:
ok single line: '6136'
Test #27:
score: 0
Accepted
time: 2ms
memory: 9324kb
input:
4 4 7471 1 4420 0 5824 4 7662
output:
15133
result:
ok single line: '15133'
Test #28:
score: 0
Accepted
time: 0ms
memory: 9664kb
input:
2 2 4872 0 6634
output:
4872
result:
ok single line: '4872'
Test #29:
score: 0
Accepted
time: 2ms
memory: 8800kb
input:
1 1 1773
output:
1773
result:
ok single line: '1773'
Test #30:
score: 0
Accepted
time: 2ms
memory: 8588kb
input:
1 0 4003
output:
0
result:
ok single line: '0'
Test #31:
score: 0
Accepted
time: 2ms
memory: 8044kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 0ms
memory: 8536kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Subtask #3:
score: 0
Runtime Error
Dependency #2:
100%
Accepted
Test #33:
score: 7
Accepted
time: 0ms
memory: 8456kb
input:
1000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 10000 1000 1000...
output:
10000000
result:
ok single line: '10000000'
Test #34:
score: 0
Accepted
time: 2ms
memory: 8832kb
input:
1000 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 1...
output:
0
result:
ok single line: '0'
Test #35:
score: -7
Runtime Error
input:
1000 977 544 801 52 926 385 778 344 867 379 929 211 964 402 849 583 804 567 836 333 873 210 767 177 955 573 378 39 425 541 548 367 921 245 809 279 962 13 865 131 795 316 980 578 875 53 954 154 386 181 787 106 862 434 900 54 811 259 903 454 791 157 943 204 836 245 882 402 934 517 857 554 958 387 975 ...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%