oj.uz

Submission #522439

# Submission time Handle Problem Language Result Execution time Memory
522439 2022-02-05T03:37:13 Z fcmalkcin Popeala (CEOI16_popeala) C++17
26 / 100
 289 ms 262148 KB 
/*#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  long long
#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


vector<ll> adj[maxn][52];
vector<ll> adj1[maxn][52];
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]);
                    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++)
        {
            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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49356 KB Output is correct
2 Correct 25 ms 50184 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 61304 KB Output is correct
2 Correct 39 ms 61296 KB Output is correct
3 Correct 41 ms 61388 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 100160 KB Output is correct
2 Correct 112 ms 118580 KB Output is correct
3 Correct 141 ms 141484 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49356 KB Output is correct
2 Correct 25 ms 50184 KB Output is correct
3 Correct 38 ms 61304 KB Output is correct
4 Correct 39 ms 61296 KB Output is correct
5 Correct 41 ms 61388 KB Output is correct
6 Correct 91 ms 100160 KB Output is correct
7 Correct 112 ms 118580 KB Output is correct
8 Correct 141 ms 141484 KB Output is correct
9 Correct 266 ms 198524 KB Output is correct
10 Correct 289 ms 244224 KB Output is correct
11 Runtime error 125 ms 262148 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -