Submission #361216

#	Time	Username	Problem	Language	Result	Execution time	Memory
361216		Sparky_09	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	131 ms	134636 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;

void usaco(string s){
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}

const ll inf = 1e18+9;
ll n, l;
ll a[209];
ll b[209];
ll dp[209][209][209][2];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
    cin >> n >> l;
    for(ll i = 1; i <= n; ++i)
        cin >> a[i];
    for(ll i = 1; i <= n; ++i)
        cin >> b[i];
    for(ll i = 0; i <= n+1; ++i)
        for(ll j = 0; j <= n+1; ++j)
            for(ll k = 0; k <= n+1; ++k)
                for(ll m = 0; m < 2; ++m)
                    dp[i][j][k][m] = inf;
    a[n+1] = l;
    dp[0][n+1][0][0] = dp[0][n+1][0][1] = 0;
    ll ans = 0;
    for(ll i = 0; i <= n+1; ++i)
        for(ll j = n+1; j >= 0; --j)
            for(ll k = 0; k <= n+1; ++k)
                for(ll st = 0; st < 2; ++st){
                    if(dp[i][j][k][st] == inf) continue;
                    ans = max(ans, k);
                    if(i+1 >= j) continue;
                    if(st == 0){
                        ll t1 = dp[i][j][k][st] + a[i+1] - a[i];
                        if(t1 <= b[i+1])
                            dp[i+1][j][k+1][st] = min(dp[i+1][j][k+1][st], t1);
                        else
                            dp[i+1][j][k][st] = min(dp[i+1][j][k][st], t1);
                        
                        ll t2 = dp[i][j][k][st] + a[i] + l-a[j-1];
                        if(t2 <= b[j-1])
                            dp[i][j-1][k+1][st^1] = min(dp[i][j-1][k+1][st^1], t2);
                        else
                            dp[i][j-1][k][st^1] = min(dp[i][j-1][k][st^1], t2);
                    }
                    else{
                        ll t1 = dp[i][j][k][st] + a[i+1] + l-a[j];
                        if(t1 <= b[i+1])
                            dp[i+1][j][k+1][st^1] = min(dp[i+1][j][k+1][st^1], t1);
                        else
                            dp[i+1][j][k][st^1] = min(dp[i+1][j][k][st^1], t1);
                        
                        ll t2 = dp[i][j][k][st] + a[j] - a[j-1];
                        if(t2 <= b[j-1])
                            dp[i][j-1][k+1][st] = min(dp[i][j-1][k+1][st], t2);
                        else
                            dp[i][j-1][k][st] = min(dp[i][j-1][k][st], t2);
                    }
                }
    cout << ans << '\n';
}

Compilation message (stderr)

ho_t3.cpp: In function 'void usaco(std::string)':
ho_t3.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   12 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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