#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define mask(i) (1<<i)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while (c < '0' || c > '9')
{
c = getchar_unlocked();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + c - '0';
c = getchar_unlocked();
}
return x;
};
void phongbeo();
const int inf = 1e18;
const int mod2 = 1e9+7;
const int mod1 = 998244353;
const int base=67;
int add(int x,int y)
{
if(x+y>=mod2) x-=mod2;
if(x+y<0) x+=mod2;
return x+y;
}
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a, b, c, d;
};
struct ie
{
int a, b, c, d, e;
};
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,limit,w,l,r,last,root,cost;
int kk,invf;
int el = 19;
main()
{
if(fopen(task".inp","r"))
{
fin(task);
//fou(task);
}
// NHP
/// cin>>s1;
// modwwe
phongbeo(),down
// checktime
}
bool cmp(ib a,ib b)
{
return a.a<b.a;
}
int dp[2][2001][2];
vector<int> v;
ib d[4001];
int dp3[2001];
int c[2001];
ib a[2001];
int dp2[2001][2001];
void phongbeo()
{
cin>>n>>m>>k;
for(int i=1; i<=n; i++)
cin>>a[i].a>>a[i].b,
v.pb(a[i].a),
v.pb(a[i].b);
sort(v.begin(),v.end());
sort(a+1,a+1+n,cmp);
for(int i=1; i<=n; i++)
a[i].a=lower_bound(v.begin(),v.end(),a[i].a)-v.begin()+1,
a[i].b=lower_bound(v.begin(),v.end(),a[i].b)-v.begin()+1,
d[a[i].a]= {i,1},
d[a[i].b]= {i,2};
s4=0;
for(int i=0; i<v.size()-1; i++)
if(d[i+1].b==2&&d[i+2].b==1)
s4+=v[i+1]-v[i];
for(int i=1; i<=n; i++)
{
if(!c[i])
{
++dem;
l=i;
dem2=0;
for(int g=0; g<=1; g++)
for(int j=0; j<=k; j++)
for(int f=0; f<2; f++)
dp[g ][j][f]=-inf;
dp[0][0][0]=0;
while(!c[l])
{
c[l]=1;
dem2=1-dem2;
dem3++;
for(int j=0; j<=k; j++)
for(int f=0; f<2; f++)
dp[dem2][j][f]=-inf;
for(int j=0; j<=k; j++)
dp[dem2][j][0]=max(dp[1-dem2][j][0],dp[1-dem2][j][1]);
for(int j=1; j<=k; j++)
dp[dem2][j][1]=max(dp[1-dem2][j-1][1]+v[a[l].a]-v[a[l].a-1],dp[1-dem2][j-1][0]);
if(i==l)
{
for(int j=1; j<=k; j++)
dp[dem2][j][1]=max(dp[1-dem2][j-1][1]+v[a[l].a]-v[a[l].a-1],dp[1-dem2][j-1][0]+v[a[l].a]-v[a[l].a-1]);
}
s3=lower_bound(v.begin(),v.end(),v[a[l].b-1])-v.begin();
if(d[s3].b==2)
{
for(int j=1; j<=k; j++)
dp[dem2][j][1]+=v[s3]-v[s3-1];
break;
}
l=d[s3].a;
}
for(int j=0; j<=dem3; j++)
{
dp2[dem][j]=max(dp[dem2][j][0],dp[dem2][j][1]);
}
c[dem]=dem3;
dem3=0;
}
}
s3=0;
for(int i=1; i<=dem; i++)
{
for(int j=s3; j>=0; j--)
for(int z=0; z<=c[i], z+j<=k; z++)
dp3[j+z]=max(dp3[j+z],dp3[j]+dp2[i][z]);
s3+=c[i];
}
s5=0;
for(int j=0; j<=k; j++)
s5=max(s5,dp3[j]);
cout<<s4+s5+m-v.back()+v[0];
}
Compilation message
keys.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
72 | main()
| ^~~~
keys.cpp: In function 'void phongbeo()':
keys.cpp:111:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=0; i<v.size()-1; i++)
| ~^~~~~~~~~~~
keys.cpp:166:27: warning: left operand of comma operator has no effect [-Wunused-value]
166 | for(int z=0; z<=c[i], z+j<=k; z++)
| ~^~~~~~
keys.cpp: In function 'int main()':
keys.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | #define fin(x) freopen(x".inp","r",stdin)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
keys.cpp:76:9: note: in expansion of macro 'fin'
76 | fin(task);
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2552 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2552 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 17 |
Correct |
2 ms |
2384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
336 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
444 KB |
Output is correct |
| 21 |
Correct |
1 ms |
336 KB |
Output is correct |
| 22 |
Correct |
1 ms |
4432 KB |
Output is correct |
| 23 |
Correct |
3 ms |
4644 KB |
Output is correct |
| 24 |
Correct |
2 ms |
4432 KB |
Output is correct |
