oj.uz

Submission #1042623

# Submission time Handle Problem Language Result Execution time Memory
1042623 2024-08-03T08:37:35 Z Theo830 Flooding Wall (BOI24_wall) C++17
0 / 100
 488 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n;
    ll a[n],b[n];
    f(i,0,n){
        cin>>a[i];
    }
    f(i,0,n){
        cin>>b[i];
        if(b[i] < a[i]){
            swap(a[i],b[i]);
        }
    }
    ll mpl[n][1005];
    ll mpr[n][1005];
    f(i,0,n){
        f(j,0,1005){
            mpl[i][j] = mpr[i][j] = 0;
        }
    }
    mpl[0][a[0]] = mpl[0][b[0]] = mpr[n-1][a[n-1]] = mpr[n-1][b[n-1]] = 1;
    f(i,1,n){
        f(j,0,1005){
            mpl[i][max(j,a[i])] += mpl[i-1][j];
            mpl[i][max(j,b[i])] += mpl[i-1][j];
            if(mpl[i][max(j,a[i])] >= INF){
               mpl[i][max(j,a[i])] -= INF;
            }
            if(mpl[i][max(j,b[i])] >= INF){
               mpl[i][max(j,b[i])] -= INF;
            }
        }
    }
    ll ans = 0;
    for(ll i = n-2;i >= 0;i--){
        f(j,0,1005){
            mpr[i][max(j,a[i])] += mpr[i+1][j];
            mpr[i][max(j,b[i])] += mpr[i+1][j];
            if(mpr[i][max(j,a[i])] >= INF){
               mpr[i][max(j,a[i])] -= INF;
            }
            if(mpr[i][max(j,b[i])] >= INF){
               mpr[i][max(j,b[i])] -= INF;
            }
        }
    }
    f(i,1,n-1){
        ll sum = 0;
        for(ll j = 1000;j >= 1;j--){
            sum += mpl[i-1][j];
            if(sum >= INF){
                sum -= INF;
            }
            ll posa = sum * mpr[i+1][j];
            posa %= INF;
            if(a[i] < j){
                ans += (j - a[i]) * posa;
                ans %= INF;
            }
            if(b[i] < j){
                ans += (j - b[i]) * posa;
                ans %= INF;
            }
        }
    }
    cout<<ans<<"\n";
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 2 ms 1732 KB Output is correct
10 Correct 180 ms 157968 KB Output is correct
11 Correct 198 ms 157576 KB Output is correct
12 Correct 179 ms 157868 KB Output is correct
13 Correct 180 ms 157712 KB Output is correct
14 Runtime error 488 ms 1048576 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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