Submission #1008133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008133		phong	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	180 ms	270192 KiB

ho_t3

#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 200 + 5, N = 3e5 + 5;
const ll oo = 1e18;
const int lg = 7, M = 4e3;
const int base = 2e5, mod = 998244353;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';cout << endl
using namespace std;

int n, m, L;
int a[nmax * 2];
ll f[nmax][nmax * 2][nmax][2];
int b[nmax * 2];

void ckmin(ll &a, ll b){
    a = min(a, b);
}
int cost(int i, int j, int x, int cur){
    if(x > j){
        x -= m;
        return ((x >= i) == 0 && b[x] >= cur);
    }
    else{
        x += m;
        return ((x <= j) == 0 && b[x] >= cur);
    }
    return 0;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//        freopen("code.inp", "r", stdin);
//        freopen("code.out", "w", stdout);
    cin >> n >> L;
    memset(f, 0x3f, sizeof f);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    a[++n] = L;
    m = n - 1;
    for(int i = 1; i <= m; ++i){
        a[++n] = a[i];
        b[n] = b[i];
    }
    ++m;
    f[m][m][0][0] = f[m][m][0][1] = 0;
//    cout << cost(m, m, m - 1, 2) << ' ';
    for(int i = m; i >= 1; --i){
        for(int j = m; j <= n; ++j){
            for(int k = 0; k <= m; ++k){
                int res = a[m] - a[i];
                if(j != m) res += a[j];
                ckmin(f[i][j][k][0], f[i][j][k][1] + res);
                ckmin(f[i][j][k][1], f[i][j][k][0] + res);
                //
                ll cur = f[i][j][k][0] + abs(a[i - 1] - a[i]);
                ckmin(f[i - 1][j][k + cost(i, j, i - 1, cur)][0], cur);
                cur = f[i][j][k][1];
                if(j == m) cur += a[j + 1];
                else cur += a[j + 1] - a[j];
                ckmin(f[i][j + 1][k + cost(i, j, j + 1, cur)][1], cur);
            }
        }
    }
//    cout << f[5][m + 1][2][1] << ' ';
    int ans = 0;
    for(int k = m; k >= 0; --k){
        for(int i = 1; i <= m; ++i){
            for(int j = m; j <= n; ++j){
                if(min(f[i][j][k][0], f[i][j][k][1]) < oo) cout << k, exit(0);
            }
        }
    }

}
/*
4 5
3 1 3 7
3 2 0 4
1 2 5 1
4 2 4 9
3 4 3 9




*/

Compilation message (stderr)

ho_t3.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      | ^~~~
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:71:9: warning: unused variable 'ans' [-Wunused-variable]
   71 |     int ans = 0;
      |         ^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75