oj.uz

Submission #285409

# Submission time Handle Problem Language Result Execution time Memory
285409 2020-08-28T22:29:36 Z loideptrai1 K blocks (IZhO14_blocks) C++14
0 / 100
 6 ms 4736 KB 
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define name ""
#define inout freopen(name".inp","r", stdin); freopen(name".out","w",stdout);

using namespace std;

const int N=1e5+10;
const int MOD=1e9+7;
const int base=257;
const int M=1e6+1;
const int INFI=1e8;

ll Hash[M], po[M];

ll gethash ( ll l , ll r )
{
    return ((Hash[r]- Hash[l-1] * po[r-l+1] + MOD* MOD ) % MOD);
}

void precomputehashing()
{
    po[0]=1;
    for(int i=1; i<=M; i++) po[i]=(po[i-1]*base) % MOD;
    string s;
    s=" "+s;
    for(int i=1; i<= s.size()-1; i++) Hash[i]=(Hash[i-1] * base + s[i] - '*' +1 ) % MOD;
}
/// C(k,n)
ll fac[N], ifac[N];

ll PowerMod(ll a, ll n)
{
	ll ret = 1;
	while (n){
		if (n & 1){
			ret *= a;
			ret %= MOD;
		}
		a *= a;
		a %= MOD;
		n /= 2;
	}
	return ret;
}

 void precomputecombinatoris()
 {
	int i;
	fac[0] = 1;
	for (i = 1; i < N; i++){
		fac[i] = (i * fac[i - 1]) % MOD;
	}
	ifac[N - 1] = PowerMod(fac[N - 1], MOD - 2);
	for (i = N - 2; i >= 0; i--){
		ifac[i] = ((i + 1) * ifac[i + 1]) % MOD;
	}
}

ll C(int r, int n)
{
	ll ret = fac[n];
	ret *= ifac[r];
	ret %= MOD;
	ret *= ifac[n - r];
	ret %= MOD;
	return ret;
}

int a[N], dp[N][110];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //inout;
    //precomputecombinatorics();
    //precomputehashing();
    int n,k;
    cin >> n >> k;
    for (int i=1; i<=n; i++){
        cin >> a[i];
    }
    for (int i=0; i<=n; i++){
        for (int j=0; j<=k; j++){
            dp[i][j]=INFI;
        }
    }
    dp[0][0]=0;
    for (int j=1; j<=k; j++){
        deque <pii> d;
        for (int i=1; i<=n; i++){
            int minv=dp[i-1][j-1];
            while (d.size() && a[d.back().first]<=a[i]){
                minv=min(minv,d.back().second);
                d.pop_back();
            }
            int pos=0;
            if (d.size()){
                pos=d.back().first;
            }
            dp[i][j]=min(dp[pos][j],minv+a[i]);
            //cout << i << " " << j << " " << dp[pos][j] << "\n";
            d.push_back(pii(j,minv));
        }
    }

    cout << dp[n][k];
    return 0;
}

Compilation message

blocks.cpp: In function 'long long int gethash(long long int, long long int)':
blocks.cpp:21:50: warning: integer overflow in expression of type 'int' results in '-371520463' [-Woverflow]
   21 |     return ((Hash[r]- Hash[l-1] * po[r-l+1] + MOD* MOD ) % MOD);
      |                                               ~~~^~~~~
blocks.cpp: In function 'void precomputehashing()':
blocks.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=1; i<= s.size()-1; i++) Hash[i]=(Hash[i-1] * base + s[i] - '*' +1 ) % MOD;
      |                  ~^~~~~~~~~~~~~
blocks.cpp:27:34: warning: iteration 1000000 invokes undefined behavior [-Waggressive-loop-optimizations]
   27 |     for(int i=1; i<=M; i++) po[i]=(po[i-1]*base) % MOD;
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~
blocks.cpp:27:19: note: within this loop
   27 |     for(int i=1; i<=M; i++) po[i]=(po[i-1]*base) % MOD;
      |                  ~^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Incorrect 0 ms 384 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4736 KB Output isn't correct
2 Halted 0 ms 0 KB -