oj.uz

Submission #590878

# Submission time Handle Problem Language Result Execution time Memory
590878 2022-07-06T12:37:13 Z andrei_boaca Popeala (CEOI16_popeala) C++14
100 / 100
 462 ms 19660 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
int dp[20005][55],rmq[55][20005],vals[20005],loga[20005];
int n,t,S;
int val[20005];
bool have[55][20005];
int nxt[55][20005],s[20005];
bool bad[55];
int mycost[55];
int need[20005][55];
bool add=1;
vector<pii> v[55];
int getmin(int st,int dr,int k)
{
    return rmq[k][dr];
}
vector<int> mypoz[20005];
bool comp(pii a, pii b)
{
    return a.second>b.second;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>t>>S;
    for(int i=1;i<=t;i++)
    {
        for(int j=0;j<=15;j++)
            if((1LL<<j)<=i)
                loga[i]=j;
    }
    for(int i=1;i<=t;i++)
    {
        cin>>val[i];
        s[i]=s[i-1]+val[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=t;j++)
        {
            char c;
            cin>>c;
            have[i][j]=c-'0';
        }
    for(int i=1;i<=n;i++)
    {
        nxt[i][0]=0;
        for(int j=1;j<=t;j++)
        {
            nxt[i][j]=nxt[i][j-1];
            if(!have[i][j])
                nxt[i][j]=j;
        }
        /*for(int j=1;j<=t;j++)
            cout<<nxt[i][j]<<' ';
        cout<<'\n';*/
    }
    for(int i=1;i<=t;i++)
    {
        for(int j=1;j<=n;j++)
            mypoz[i].push_back(nxt[j][i]);
        sort(mypoz[i].begin(),mypoz[i].end());
        reverse(mypoz[i].begin(),mypoz[i].end());
    }
    dp[0][0]=0;
    for(int i=1;i<=S;i++)
        dp[0][i]=2e9;
    for(int i=1;i<=t;i++)
        dp[i][0]=2e9;
    for(int k=0;k<=n;k++)
    {
        for(int i=0;i<=t;i++)
            vals[i]=dp[i][0]-k*s[i];
        for(int i=0;i<=t;i++)
        {
            rmq[k][i]=vals[i];
            if(i>0)
                rmq[k][i]=min(rmq[k][i],rmq[k][i-1]);
        }
    }
    for(int a=1;a<=S;a++)
    {
        for(int i=1;i<=t;i++)
        {
            dp[i][a]=2e9;
            /*for(int k=i-1;k>=0;k--)
                dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k+1][i]);*/
        }
        for(int i=1;i<=t;i++)
        {
            dp[i][a]=2e9;
            int cnt=n;
            int cur=i;
            for(int j=0;j<mypoz[i].size();j++)
            {
                int poz=mypoz[i][j];
                int st=poz;
                int dr=cur-1;
                if(st<=dr)
                {
                    int nr=getmin(0,dr,cnt)+cnt*s[i];
                    dp[i][a]=min(dp[i][a],nr);
                }
                cur=poz;
                cnt--;
            }
            int st=0;
            int dr=cur-1;
            if(st<=dr)
            {
                int nr=getmin(0,dr,cnt)+cnt*s[i];
                dp[i][a]=min(dp[i][a],nr);
            }
        }
        for(int k=0;k<=n;k++)
        {
            for(int i=0;i<=t;i++)
                vals[i]=dp[i][a]-k*s[i];
            for(int i=0;i<=t;i++)
            {
                rmq[k][i]=vals[i];
                if(i>0)
                    rmq[k][i]=min(rmq[k][i],rmq[k][i-1]);
            }
        }
        add=0;
    }
    for(int i=1;i<=S;i++)
        cout<<dp[t][i]<<'\n';
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:96:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for(int j=0;j<mypoz[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
popeala.cpp:33:23: warning: array subscript 32768 is above array bounds of 'int [20005]' [-Warray-bounds]
   33 |                 loga[i]=j;
      |                 ~~~~~~^
popeala.cpp:5:46: note: while referencing 'loga'
    5 | int dp[20005][55],rmq[55][20005],vals[20005],loga[20005];
      |                                              ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1876 KB Output is correct
2 Correct 10 ms 1876 KB Output is correct
3 Correct 12 ms 1920 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3412 KB Output is correct
2 Correct 69 ms 4260 KB Output is correct
3 Correct 89 ms 5196 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 14 ms 1876 KB Output is correct
4 Correct 10 ms 1876 KB Output is correct
5 Correct 12 ms 1920 KB Output is correct
6 Correct 47 ms 3412 KB Output is correct
7 Correct 69 ms 4260 KB Output is correct
8 Correct 89 ms 5196 KB Output is correct
9 Correct 138 ms 7536 KB Output is correct
10 Correct 185 ms 9428 KB Output is correct
11 Correct 424 ms 19352 KB Output is correct
12 Correct 448 ms 19628 KB Output is correct
13 Correct 452 ms 19660 KB Output is correct
14 Correct 455 ms 19632 KB Output is correct
15 Correct 462 ms 19648 KB Output is correct