Submission #859425

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
859425	2023-10-10T06:50:01 Z	Tudy006	Peru (RMI20_peru)	C++14	Compilation error	0 ms	0 KB

peru

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2500000;
const int BSIZE = 1e4;
const int MOD = 1e9 + 7;

//char buf[BSIZE];
//int ix = BSIZE;

//FILE* fin = fopen( "peru.in", "r" );
//ofstream fout( "peru.out" );

//static inline char get_ch() {
//    if ( ix == BSIZE ) {
//        fread( buf, 1, BSIZE, fin );
//        ix = 0;
//    }
//    return buf[ix++];
//}
//inline int get_int() {
//    int x = 0;
//    char ch;
//    while ( !isdigit( ch = get_ch() ) );
//    do {
//        x = x * 10 + ch - '0';
//    } while ( isdigit( ch = get_ch() ) );
//    return x;
//}

int v[NMAX + 1];
long long dp[NMAX + 1];

deque <int> dq;
deque <pair<int, int>> dq2;

int main() {
    int n, k, t;
//    cin >> t;
    cin >> n >> k;
//    n = get_int();
//    k = get_int();
    for ( int i = 1; i <= n; i ++ ) {
//        v[i] = get_int();
        cin >> v[i];
    }

    for ( int i = 1; i <= k; i ++ ) {
        while ( !dq.empty() && v[dq.back()] <= v[i] ) {
            if ( dq.size() >= 2 && !dq2.empty() && dq2.back().first == dq[dq.size() - 2] && dq2.back().second == dq.back() )
                dq2.pop_back();
            dq.pop_back();

        }
        dq.push_back( i );
        if ( dq.size() > 1 ) {
            int aux1 = dq[dq.size() - 2], aux2 = i;
            while ( !dq2.empty() && dp[dq2.back().first] + v[dq2.back().second] >= dp[aux1] + v[aux2] )
                dq2.pop_back();
            dq2.push_back( { aux1, aux2 } );
        }
        dp[i] = v[dq.front()];
    }
//    cout << "OK" << endl;
    for ( int i = k + 1; i <= n; i ++ ) {
        while ( !dq.empty() && v[dq.back()] <= v[i] ) {
            if ( dq.size() >= 2 && !dq2.empty() && dq2.back().first == dq[dq.size() - 2] && dq2.back().second == dq.back() )
                dq2.pop_back();
            dq.pop_back();
        }
        dq.push_back( i );
        while ( dq.front() <= i - k ) dq.pop_front();

        dp[i] = dp[i - k] + v[dq.front()];

        if ( dq.size() > 1 ) {
            int aux1 = dq[dq.size() - 2], aux2 = i;
            while ( !dq2.empty() && dp[dq2.back().first] + v[dq2.back().second] >= dp[aux1] + v[aux2] )
                dq2.pop_back();
            dq2.push_back( { aux1, aux2 } );

            while ( dq2.front().first <= i - k ) dq2.pop_front();
            if ( t == 1 )
            dp[i] = min( dp[i], dp[dq2.front().first] + v[dq2.front().second] );

        }
        if ( t == 2 )
        for ( int j = 0; j + 1 < dq.size(); j ++ ) {
            dp[i] = min( dp[i], dp[dq[j]] + v[dq[j + 1]] );
        }
    }
    int p23 = 1, ans = 0;
    for ( int i = n; i >= 1; i -- ) {
        ans += dp[i] % MOD * p23 % MOD;
        if ( ans >= MOD ) ans -= MOD;
        p23 = (long long)p23 * 23 % MOD;
//        cout << dp[n - i + 1] << ' ';
    }
//    cout << endl;
    cout << ans;
//    fout << endl << ans;
    return 0;
}

Compilation message

peru.cpp: In function 'int main()':
peru.cpp:89:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for ( int j = 0; j + 1 < dq.size(); j ++ ) {
      |                          ~~~~~~^~~~~~~~~~~
peru.cpp:84:13: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |             if ( t == 1 )
      |             ^~
/usr/bin/ld: /tmp/cc7cmLax.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccqOOqDt.o:peru.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc7cmLax.o: in function `main':
grader.cpp:(.text.startup+0x144): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status