oj.uz

Submission #860326

# Submission time Handle Problem Language Result Execution time Memory
860326 2023-10-12T15:22:04 Z nnhzzz Popeala (CEOI16_popeala) C++14
100 / 100
 325 ms 18264 KB 
// cre: Nguyen Ngoc Hung - Train VOI 2024 :>
 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>
 
using namespace std;
 
#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define                ll  long long
#define                vi  vector<int>
#define               vvi  vector<vi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
#define               int  ll
//-------------------------------------------------------------//
const int inf = 1e12,LOG = 20,MAXN = 2e4+3,N = 53;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
 
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/
 
int sum[MAXN],f[MAXN],pre[MAXN][N],dp[MAXN][N];
int n,t,s;
 
void solve(){
    cin >> n >> t >> s;
    REP(i,1,t){
        cin >> sum[i];
        sum[i] += sum[i-1];
    }
    REP(i,1,n){
        REP(j,1,t){
            char ch; cin >> ch;
            pre[j][i] = ch=='1'?pre[j-1][i]:j;
        }
    }
    REP(i,1,t){
        pre[i][0] = i;
        sort(pre[i],pre[i]+n+1);
    }
    memset(dp,0x3f,sizeof dp);
    dp[0][0] = 0;
    REP(i,1,s){
        REP(j,0,n) f[j] = inf;
        REP(j,1,t){
            REP(k,0,n){
                REP(l,pre[j-1][k],pre[j][k]-1) mini(f[k],dp[l][i-1]-sum[l]*k);
                mini(dp[j][i],f[k]+sum[j]*k);
            }
        }
        cout << dp[t][i] << "\n";
    }
}
 
__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "nnhzzz"
    if(fopen(name1".inp","r")){
        freopen(name1".inp","r",stdin);
        freopen(name1".out","w",stdout);
    }
 
    int test = 1;
 
    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 4 ms 8636 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10844 KB Output is correct
2 Correct 10 ms 10836 KB Output is correct
3 Correct 11 ms 10844 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10844 KB Output is correct
2 Correct 59 ms 11072 KB Output is correct
3 Correct 64 ms 11132 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 4 ms 8636 KB Output is correct
3 Correct 11 ms 10844 KB Output is correct
4 Correct 10 ms 10836 KB Output is correct
5 Correct 11 ms 10844 KB Output is correct
6 Correct 41 ms 10844 KB Output is correct
7 Correct 59 ms 11072 KB Output is correct
8 Correct 64 ms 11132 KB Output is correct
9 Correct 81 ms 13340 KB Output is correct
10 Correct 157 ms 13460 KB Output is correct
11 Correct 235 ms 18260 KB Output is correct
12 Correct 242 ms 18260 KB Output is correct
13 Correct 306 ms 18260 KB Output is correct
14 Correct 325 ms 18264 KB Output is correct
15 Correct 321 ms 18264 KB Output is correct