oj.uz

Submission #555092

# Submission time Handle Problem Language Result Execution time Memory
555092 2022-04-30T07:13:14 Z kwongweng Boat (APIO16_boat) C++17
0 / 100
 2000 ms 485120 KB 
/*
Solution for APIO 2016 - Boat
Tags : 
*/

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}

void solve(){
    int n; cin >> n;
    vector<ll> a(n), b(n); FOR(i,0,n) cin >> a[i] >> b[i];
    vector<ll> dp[n];
    vector<ll> pre[n];
    map<ll, ll> mp;
    ll ans = 0;
    FOR(i,0,n){
        dp[i].pb(1);
        FOR(j,0,i){
            dp[i][0] += pre[j][min(b[j]-a[j], a[i]-a[j])];
            dp[i][0] %= MOD;
        }
        FOR(j,a[i], b[i]){
            ll val = (dp[i][j-a[i]] + mp[j]) % MOD;
            dp[i].pb(val);
        }
        pre[i].pb(0);
        FOR(j,a[i],b[i]+1){
            ll val = (pre[i][j-a[i]] + dp[i][j-a[i]]) % MOD;
            pre[i].pb(val);
            ll val2 = (mp[j] + dp[i][j-a[i]]) % MOD;
            mp[j] = val2;
        }
        ans = (ans + pre[i][b[i]-a[i]+1]) % MOD;
    }
    cout << ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

Compilation message

boat.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("Ofast")
      | 
boat.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2114 ms 485120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -