Submission #522440

#	Time	Username	Problem	Language	Result	Execution time	Memory
522440		fcmalkcin	Popeala (CEOI16_popeala)	C++17	100 / 100	689 ms	230580 KiB

popeala

/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>
using namespace std;

#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define For(i,a,b) for (ll i=a;i<=b;i++)

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e4+100;
const ll mod=998244353  ;
const ll base=2e9+10000;

/// you will be the best but now you just are trash
/// goal 3/7

ll f[maxn];
char a[53][maxn];
ll nxt[53][maxn];
ll dp[maxn][53];
ll dp1[maxn][53][53];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("popeala.inp", "r"))
    {
        freopen("popeala.inp", "r", stdin);
        freopen("popeala.out", "w", stdout);
    }
    ll n, t, s;
    cin>> n>> t>> s;
    for (int i=1; i<=t; i++)
    {
        ll x;
        cin>> x;
        f[i]=f[i-1]+x;
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=t; j++)
        {
            cin>> a[i][j];
        }
        for (int j=t; j>=1; j--)
        {
            if (a[i][j]=='1')
                nxt[i][j]=nxt[i][j+1]+1;
            else
                nxt[i][j]=0;
        }
    }
    for (int p=0; p<=t; p++)
    {
        for (int j=0; j<=s; j++)
        {
            dp[p][j]=base;
            for (int h=0; h<=n; h++)
            {
                dp1[p][j][h]=base;
            }
        }
    }
    dp[0][0]=0;
    for (int i=1; i<=t+1; i++)
    {
        vector<ll> vt;
        for (int h=1; h<=n; h++)
        {
            vt.pb(nxt[h][i]);
        }
        sort(vt.begin(),vt.end());
        if (i>=2)
        {
            for (int j=0; j<=s; j++)
            {
                for (int t=0; t<=n; t++)
                {
                    dp1[i-1][j][t]=min(dp1[i-1][j][t],dp1[i-2][j][t]);
                    if (dp1[i-1][j][t]!=base) dp[i-1][j]=min(dp[i-1][j],dp1[i-1][j][t]+f[i-1]*t);
                }
            }
        }
        if (i==t+1) break;
        for (int j=0; j<=s; j++)
        {
            if (dp[i-1][j]==base) continue;
            dp1[i+vt.back()][j+1][0]=min(dp1[i+vt.back()][j+1][0],dp[i-1][j]-0*f[i-1]);
            ll sl=0;
            for (int t=vt.size()-1;t>=0;t--)
            {
                sl++;
                ll pre=0;
                if (t)
                {
                    pre=vt[t-1];
                }
                dp1[i+pre][j+1][sl]=min(dp1[i+pre][j+1][sl],dp[i-1][j]-sl*f[i-1]);
            }
        }
    }
    for(int h=1;h<=s;h++)
    {
        cout <<dp[t][h]<<endl;
    }
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen("popeala.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen("popeala.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74