oj.uz

답안 #590848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590848 2022-07-06T12:17:22 Z andrei_boaca 조교 (CEOI16_popeala) C++14
100 / 100
 1974 ms 88948 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
int dp[20005][55],rmq[55][16][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)
{
    int l=loga[dr-st+1];
    int rez=min(rmq[k][l][st],rmq[k][l][dr-(1<<l)+1]);
    if(add)
        v[k].push_back({st,dr});
    return rez;
}
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=t;i>=0;i--)
        {
            rmq[k][0][i]=vals[i];
            for(int j=1;j<=15;j++)
            {
                int poz=i+(1LL<<(j-1))-1;
                if(poz>t)
                    break;
                rmq[k][j][i]=rmq[k][j-1][i];
                if(poz+1<=t)
                    rmq[k][j][i]=min(rmq[k][j][i],rmq[k][j-1][poz+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(st,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(st,dr,cnt)+cnt*s[i];
                dp[i][a]=min(dp[i][a],nr);
            }
        }
        for(int k=0;k<=n;k++)
        {
            if(add)
            {
                sort(v[k].begin(),v[k].end(),comp);
                int poz=t;
                for(pii a:v[k])
                {
                    int st=a.first,dr=a.second;
                    while(poz>=st)
                    {
                        need[poz][k]=dr;
                        poz--;
                    }
                }
            }
            for(int i=0;i<=t;i++)
                vals[i]=dp[i][a]-k*s[i];
            for(int i=t;i>=0;i--)
            {
                rmq[k][0][i]=vals[i];
                for(int j=1;j<=loga[need[i][k]]+1;j++)
                {
                    int poz=i+(1LL<<(j-1))-1;
                    if(poz>t)
                        break;
                    rmq[k][j][i]=rmq[k][j-1][i];
                    if(poz+1<=t)
                        rmq[k][j][i]=min(rmq[k][j][i],rmq[k][j-1][poz+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:107:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             for(int j=0;j<mypoz[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
popeala.cpp:37:23: warning: array subscript 32768 is above array bounds of 'int [20005]' [-Warray-bounds]
   37 |                 loga[i]=j;
      |                 ~~~~~~^
popeala.cpp:5:50: note: while referencing 'loga'
    5 | int dp[20005][55],rmq[55][16][20005],vals[20005],loga[20005];
      |                                                  ^~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 852 KB Output is correct
2 Correct 2 ms 2260 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 4948 KB Output is correct
2 Correct 32 ms 4936 KB Output is correct
3 Correct 34 ms 4984 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 11472 KB Output is correct
2 Correct 242 ms 15248 KB Output is correct
3 Correct 321 ms 19268 KB Output is correct

Subtask #4
74.0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 852 KB Output is correct
2 Correct 2 ms 2260 KB Output is correct
3 Correct 34 ms 4948 KB Output is correct
4 Correct 32 ms 4936 KB Output is correct
5 Correct 34 ms 4984 KB Output is correct
6 Correct 160 ms 11472 KB Output is correct
7 Correct 242 ms 15248 KB Output is correct
8 Correct 321 ms 19268 KB Output is correct
9 Correct 530 ms 29900 KB Output is correct
10 Correct 737 ms 38236 KB Output is correct
11 Correct 1824 ms 85152 KB Output is correct
12 Correct 1964 ms 88948 KB Output is correct
13 Correct 1974 ms 87392 KB Output is correct
14 Correct 1908 ms 87600 KB Output is correct
15 Correct 1968 ms 87772 KB Output is correct