| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1238769 | modwwe | Pinball (JOI14_pinball) | C++17 | 0 ms | 0 KiB |
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r)
{
return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const int inf = 1e9;
const int mod2 = 1e9 + 7;
//const ll base=67;
int n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,
r2, center;
int i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, now, root, q, en;
int el = 19;
main()
{
///top1apio
if (fopen(task2".inp", "r"))
{
fin(task2);
fou(task2);
}
///top1apio
if (fopen(task".inp", "r"))
{
fin(task);
fou(task);
}
///top1apio
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
// cin>>s1;
//9 ll t;cin>>t;while(t--)
phongbeo();
/// checktime
///top1apio
}
int dp[2007][2007],d[2007][2007],c[2007][2007];
struct ib{int a,b;}
ib a[2007];
int nxt[2007];
bool cmp(ib a,ib b)
{
return a.b<b.b;
}
void go(int x,int y,int val,int mx)
{
if(dem>k)return;
if(x==0&&d[1][s2]<=mx)
{
dem++;
}
else return;
if(y==s2)return;
bool ok=0;
for(int i=x+1; i<=n; i++)
{
if(d[i][y+1]+val>mx)break;
if(a[i].b>=y+1&&c[i][y+1]+val<=mx)
{
dem+=ok;
ok=1;
go(i,y+1,val+a[i].a,mx);
}
if(dem>k)return;
}
}
void work(int x,int y,int val,int hihi,int mx)
{
if(y==hihi)
{
v.pb({y,mx});
return;
}
if(hihi==s2)
{
for(int i=x+1; i<=n; i++)
if(a[i].b>=y+1&&c[i][y+1]+val<=mx)
work(i,y+1,val+a[i].a,hihi,mx);
}
else
{
for(int i=x+1;i<=n;i++)
if(a[i].b>=y+1&&dp[i][y+1]+y+1>=hihi)
work(i,y+1,0,hihi,0);
}
}
bool check(int x)
{
dem=0;
go(0,0,0,x);
if(dem>k)return 1;
return 0;
}
void phongbeo()
{
cin>>n>>k;
for(int i=1; i<=n; i++)
cin>>a[i].a>>a[i].b;
sort(a+1,a+1+n,cmp);
for(int i=1; i<=n+1; i++)
nxt[i]=n+1;
for(int i=n; i>=1; --i)
nxt[a[i].b]=i;
for(int i=n; i>=1; --i)
if(nxt[i]==n+1)nxt[i]=nxt[i+1];
dp[1][1]=1;
for(int i=1; i<n; i++)
for(int j=1; j<=i; j++)
{
s3=nxt[j+1];
if(s3>i)dp[s3][j+1]+=dp[i][j];
else dp[i+1][j+1]+=dp[i][j];
dp[i+1][j]+=dp[i][j];
}
for(int i=2; i<=n; i++)
for(int j=1; j<=i-1; j++)
dp[i][j]+=dp[i][j-1];
for(int i=n; i>=1; --i)
{
if(dp[n][i]<=k)
{
k-=dp[n][i];
}
else
{
s2=i;
break;
}
}
memset(dp,0,sizeof dp);
for(int i=n; i>=2; --i)
for(int j=2; j<=a[i].b; j++)
{
s3=nxt[j-1];
dp[i-1][j-1]=dp[i][j]+1;
}
for(int i=1; i<=n; i++)
if(a[i].b<=s2)
c[i][s2]=a[i].a;
for(int i=1; i<=n; i++)
for(int j=1; j<=s2; j++)
c[i][j]=inf;
for(int i=1; j<=s2; j++)
d[n][i]=c[n][i];
for(int i=n-1; i>=1; --i)
for(int j=1; j<=s2; j++)
{
s3=nxt[j+1];
if(s3==n+1)continue;
if(j<=a[i].b)
{
if(s3>i)c[i][j]=min(c[i][j],d[s3][j+1]+a[i].a);
else c[i][j]=min(c[i][j],d[i+1][j+1]+a[i].a);
}
d[i][j]=min(d[i+1][j],c[i][j]);
}
if(k==0)r=-1;
l=0;
r=s2*1e9-1;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid))r=mid-1;
else l=mid+1;
}
work(0,0,0,s2+1,0);
work(0,0,0,s2,r);
}