Submission #1238793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238793		modwwe	Akcija (COCI21_akcija)	C++20	90 / 110	5096 ms	95284 KiB

Main

#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 = 1e18;
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;
    // 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];
vector<ib> v;
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][1]<=mx)
    {
        dem++;
    }
    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&&hihi!=s2)
    {
        v.pb({y,val});
    }
    if(y==hihi&&hihi==s2)
    {
        v.pb({y,val});
        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,val+a[i].a,hihi,0);

            }
    }
}
bool check(int x)
{
    dem=0;
    go(0,0,0,x);
    if(dem>=k)return 1;
    return 0;
}
bool cmpp(ib a,ib b)
{
    if(a.a==b.a)return a.b<b.b;
    return a.a>b.a;
}
void phongbeo()
{
    cin>>n>>k;
    s9=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]=min(k+1,dp[i][j]+dp[s3][j+1]);
            else dp[i+1][j+1]=min(k+1,dp[i][j]+dp[i+1][j+1]);
            dp[i+1][j]=min(k+1,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]=min(k+1,dp[i][j]+dp[i-1][j]);
    for(int i=n; i>=1; --i)
    {
        if(dp[n][i]<=k)
        {
            k-=dp[n][i];
        }
        else
        {
            s2=i;
            break;
        }
    }
    memset(dp,-1,sizeof dp);
    memset(d,-1,sizeof d);
    for(int i=1; i<=a[n].b; i++)
        dp[n][i]=0,d[n][i]=0;
    for(int i=n-1; i>=1; --i)
        for(int j=1; j<=a[i].b; j++)
        {
            s3=nxt[j+1];
            if(s3>i)dp[i][j]=d[s3][j+1]+1;
            else dp[i][j]=d[i+1][j+1]+1;
            d[i][j]=max(d[i+1][j],dp[i][j]);
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=s2; j++)
            c[i][j]=inf;
    for(int i=1; i<=n; i++)
        if(a[i].b>=s2)
            c[i][s2]=a[i].a;
    for(int i=1; i<=s2; i++)
        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];
            d[i][j]=min(d[i+1][j],c[i][j]);
            if(s3==n+1)continue;
            if(j<=a[i].b&&j!=s2)
            {
                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);
    if(s2!=0)work(0,0,0,s2,r);
    sort(v.begin(),v.end(),cmpp);
     while(v.size()<s9)
        v.pb({s2,r+1});
    for(auto x:v)
        cout<<x.a<<" "<<x.b,down
    }

Compilation message (stderr)

Main.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:38:9: note: in expansion of macro 'fin'
   38 |         fin(task2);
      |         ^~~
Main.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 fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:39:9: note: in expansion of macro 'fou'
   39 |         fou(task2);
      |         ^~~
Main.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:45:9: note: in expansion of macro 'fin'
   45 |         fin(task);
      |         ^~~
Main.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 fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:46:9: note: in expansion of macro 'fou'
   46 |         fou(task);
      |         ^~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 30 / 30
• Subtask 6: 0 / 20