# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
411166 |
2021-05-24T13:01:35 Z |
반딧불(#7588) |
여별 열쇠 (JOI15_keys) |
C++14 |
|
1 ms |
460 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dat{
int x, t, m; /// m=0: start, m=1: end
dat(){}
dat(int x, int t, int m): x(x), t(t), m(m){}
bool operator<(const dat &r)const{
return t<r.t;
}
};
vector<dat> vec;
int n, m, k;
int s[2002], e[2002];
int ans;
int weight[2002];
vector<pair<int, int> > link[2002];
int renum[2002], loc[2002], locCnt;
int w[2002], bet[2002];
int DP[2002][2002][2];
int basic;
void dfsRenum(int x){
int tmp = ++locCnt;
renum[tmp] = x;
loc[x] = tmp;
w[tmp] = weight[x];
for(auto y: link[x]){
if(loc[y.first]) continue;
bet[tmp] = y.second;
dfsRenum(y.first);
}
}
int main(){
scanf("%d %d %d", &n, &m, &k);
for(int i=1; i<=n; i++){
scanf("%d %d", &s[i], &e[i]);
vec.push_back(dat(i, s[i], 0));
vec.push_back(dat(i, e[i], 1));
}
sort(vec.begin(), vec.end());
basic = vec[0].t;
for(int i=0; i<2*n-1; i++){
dat p = vec[i], q = vec[i+1];
if(!p.m && !q.m) weight[p.x] += q.t - p.t;
else if(p.m && q.m) weight[q.x] += q.t - p.t;
else if(!p.m && q.m){
link[p.x].push_back(make_pair(q.x, q.t - p.t));
if(p.x != q.x) link[q.x].push_back(make_pair(p.x, q.t - p.t));
}
else basic += q.t - p.t;
}
weight[vec.back().x] += m - vec.back().t;
for(int i=1; i<=n; i++){
if((int)link[i].size() >= 2 || loc[i]) continue;
dfsRenum(i);
}
assert(locCnt == n);
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
DP[i][j][0] = max(DP[i-1][j][0], DP[i-1][j][1]);
DP[i][j][1] = max(DP[i-1][j-1][0] + w[i], DP[i-1][j-1][1] + w[i] + bet[i-1]);
}
}
printf("%d", max(DP[n][k][0], DP[n][k][1]) + basic);
}
Compilation message
keys.cpp: In function 'int main()':
keys.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | scanf("%d %d %d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
keys.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d %d", &s[i], &e[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |