oj.uz

Submission #589833

# Submission time Handle Problem Language Result Execution time Memory
589833 2022-07-05T10:46:44 Z andrei_boaca Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 12388 KB 
#include <bits/stdc++.h>

using namespace std;
int dp[20005][55];
int n,t,S;
int val[20005];
bool have[55][20005];
int nxt[55][20005],s[20005];
bool bad[55];
int mycost[55];
struct ev
{
    bool add;
    int poz,val;
};
vector<ev> events[55];
bool comp(ev a, ev b)
{
    return a.poz<b.poz;
}
multiset<int> setik[55];
int p[55];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>t>>S;
    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][t+1]=t+1;
        for(int j=t;j>=1;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';*/
    }
    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 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=0;i<=n;i++)
        {
            events[i].clear();
            setik[i].clear();
            p[i]=0;
        }
        for(int i=1;i<=t;i++)
        {
            vector<int> vals;
            for(int j=1;j<=n;j++)
                vals.push_back(nxt[j][i]);
            sort(vals.begin(),vals.end());
            int nr=dp[i-1][a-1]-s[i-1]*n;
            int cnt=n;
            int cur=i;
            for(int j=0;j<vals.size();j++)
            {
                int poz=vals[j];
                int st=cur;
                int dr=poz-1;
                if(st<=dr)
                {
                    events[cnt].push_back({1,st,nr});
                    events[cnt].push_back({0,dr+1,nr});
                }
                cur=poz;
                cnt--;
                nr+=s[i-1];
            }
            if(cur<=t)
            {
                events[cnt].push_back({1,cur,nr});
                events[cnt].push_back({0,t+1,nr});
            }
        }
        for(int i=0;i<=n;i++)
            sort(events[i].begin(),events[i].end(),comp);
        for(int i=1;i<=t;i++)
        {
            bool ok=0;
            if(i==t)
                ok=1;
            for(int nr=0;nr<=n;nr++)
            {
                while(p[nr]<events[nr].size()&&events[nr][p[nr]].poz<=i)
                {
                    int val=events[nr][p[nr]].val;
                    bool add=events[nr][p[nr]].add;
                    if(add)
                        setik[nr].insert(val);
                    else
                        setik[nr].erase(setik[nr].find(val));
                    p[nr]++;
                }
                if(setik[nr].size())
                {
                    int x=*setik[nr].begin();
                    x+=nr*s[i];
                    dp[i][a]=min(dp[i][a],x);
                }
            }
        }
    }
    for(int i=1;i<=S;i++)
        cout<<dp[t][i]<<'\n';
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(int j=0;j<vals.size();j++)
      |                         ~^~~~~~~~~~~~
popeala.cpp:110:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ev>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |                 while(p[nr]<events[nr].size()&&events[nr][p[nr]].poz<=i)
      |                       ~~~~~^~~~~~~~~~~~~~~~~~
popeala.cpp:105:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  105 |             bool ok=0;
      |                  ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 592 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 1640 KB Output is correct
2 Correct 188 ms 1624 KB Output is correct
3 Correct 179 ms 1640 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 4272 KB Output is correct
2 Correct 1232 ms 5860 KB Output is correct
3 Correct 1918 ms 7628 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 175 ms 1640 KB Output is correct
4 Correct 188 ms 1624 KB Output is correct
5 Correct 179 ms 1640 KB Output is correct
6 Correct 813 ms 4272 KB Output is correct
7 Correct 1232 ms 5860 KB Output is correct
8 Correct 1918 ms 7628 KB Output is correct
9 Execution timed out 2087 ms 12388 KB Time limit exceeded
10 Halted 0 ms 0 KB -