QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #24593 | #2556. Yet Another Interval Graph Problem | yuyue | WA | 3ms | 5792kb | C++17 | 1.6kb | 2022-04-01 13:38:59 | 2022-04-30 06:15:43 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define SZ(x) ((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define DF(i,a,b) for (int i=(a);i>=(b);--i)
//#define mp make_pair
//#define OO(x) fixed<<setprecision(x)
using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int read(){
char ch=getchar(); int w=1,c=0;
for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
return w*c;
}
const int M=5050;
int n,k,L[M],R[M],a[M],t[M],num[M][M],ct;
LL dp[M],val[M];
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read(); k=read();
F(i,1,n){
L[i]=read(); R[i]=read(); t[++ct]=L[i]; t[++ct]=R[i]; a[i]=read();
}
sort(t+1,t+ct+1);
int N=unique(t+1,t+ct+1)-t-1;
F(i,1,n){
L[i]=lower_bound(t+1,t+N+1,L[i])-t;
R[i]=lower_bound(t+1,t+N+1,R[i])-t;
F(j,L[i],R[i]-1) val[j]+=a[i];
num[L[i]][R[i]]++;
// cerr<<L[i]<<" "<<R[i]<<" interval\n";
}
DF(i,N,1) F(j,1,N) num[i][j]+=num[i+1][j];
F(i,1,N) F(j,1,N) num[i][j]+=num[i][j-1];
dp[0]=0;
F(i,1,N){
dp[i]=1e18;
F(j,0,i-1){
if (num[j+1][i]<=k)
dp[i]=min(dp[i],dp[j]+val[i]);//,cerr<<j<<" "<<i<<" "<<num[j+1][i]<<" oooooo\n";
}
// cerr<<val[i]<<" "<<dp[i]<<"\n";
}
cout<<dp[N]<<"\n";
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 3656kb
input:
5 2 1 4 1 3 6 2 5 8 5 7 10 2 9 12 1
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
5 1 2 6 5 4 6 2 8 8 5 1 3 4 6 8 7
output:
12
result:
ok single line: '12'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3608kb
input:
1 1 260947663 693934985 986106006
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 3ms
memory: 3692kb
input:
2 2 148610427 148610427 611594176 148610427 148610427 241979785
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 3ms
memory: 5792kb
input:
2 2 189944467 208945642 113891402 208945642 235053342 250664551
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3760kb
input:
2 2 259102823 862504466 73871288 91533165 259102823 447104717
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
2 2 634621570 811155007 87507743 299710238 563644023 98163867
output:
0
result:
ok single line: '0'
Test #8:
score: -100
Wrong Answer
time: 3ms
memory: 3752kb
input:
13 5 385168347 385168347 99054846 385168347 385168347 350748474 385168347 385168347 354902398 385168347 385168347 585042031 385168347 385168347 292548257 385168347 385168347 440215041 385168347 385168347 672336022 385168347 385168347 47484008 385168347 385168347 169165503 385168347 385168347 7956210...
output:
1000000000000000000
result:
wrong answer 1st lines differ - expected: '1929854426', found: '1000000000000000000'