oj.uz

Submission #741945

# Submission time Handle Problem Language Result Execution time Memory
741945 2023-05-15T06:53:45 Z vjudge1 Boat (APIO16_boat) C++17
9 / 100
 549 ms 2456 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 100;
const ll INF = (1ll<<61);
const int MOD = 1e9 + 7;
const int inf = (1<<30);
const int maxl = 20;
const int P = 31;

int n;
int a[maxn];
int b[maxn];
int dp[550][1010];

void test(){
    cin >> n;
    vector<int> v;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        v.push_back(a[i]);
        v.push_back(b[i] + 1);
    }
    v.push_back(1e9 + 1);
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < v.size() - 1; j++){
            dp[i][j] = 1;
            for(int k = 1; k < i; k++){
                if(j) dp[i][j] = (dp[i][j] + dp[k][j-1]) % MOD;
            }
            dp[i][j] = (1ll * dp[i][j] * (v[j + 1] - v[j])) % MOD;
            if(v[j] < a[i] || v[j+1] - 1 > b[i]) dp[i][j] = 0;
            ans = (ans + dp[i][j]) % MOD;
            if(j) dp[i][j] += dp[i][j-1];
        }
    }
    cout << ans << ent;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while(t--) test();
}

Compilation message

boat.cpp: In function 'void test()':
boat.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int j = 0; j < v.size() - 1; j++){
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 2260 KB Output is correct
2 Correct 474 ms 2456 KB Output is correct
3 Correct 477 ms 2236 KB Output is correct
4 Correct 496 ms 2352 KB Output is correct
5 Correct 507 ms 2264 KB Output is correct
6 Correct 461 ms 2300 KB Output is correct
7 Correct 466 ms 2332 KB Output is correct
8 Correct 471 ms 2376 KB Output is correct
9 Correct 471 ms 2316 KB Output is correct
10 Correct 485 ms 2212 KB Output is correct
11 Correct 481 ms 2320 KB Output is correct
12 Correct 495 ms 2240 KB Output is correct
13 Correct 513 ms 2420 KB Output is correct
14 Correct 498 ms 2220 KB Output is correct
15 Correct 549 ms 2208 KB Output is correct
16 Correct 85 ms 2252 KB Output is correct
17 Correct 92 ms 2252 KB Output is correct
18 Correct 88 ms 2224 KB Output is correct
19 Correct 89 ms 2188 KB Output is correct
20 Correct 98 ms 2284 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 2260 KB Output is correct
2 Correct 474 ms 2456 KB Output is correct
3 Correct 477 ms 2236 KB Output is correct
4 Correct 496 ms 2352 KB Output is correct
5 Correct 507 ms 2264 KB Output is correct
6 Correct 461 ms 2300 KB Output is correct
7 Correct 466 ms 2332 KB Output is correct
8 Correct 471 ms 2376 KB Output is correct
9 Correct 471 ms 2316 KB Output is correct
10 Correct 485 ms 2212 KB Output is correct
11 Correct 481 ms 2320 KB Output is correct
12 Correct 495 ms 2240 KB Output is correct
13 Correct 513 ms 2420 KB Output is correct
14 Correct 498 ms 2220 KB Output is correct
15 Correct 549 ms 2208 KB Output is correct
16 Correct 85 ms 2252 KB Output is correct
17 Correct 92 ms 2252 KB Output is correct
18 Correct 88 ms 2224 KB Output is correct
19 Correct 89 ms 2188 KB Output is correct
20 Correct 98 ms 2284 KB Output is correct
21 Incorrect 428 ms 2244 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 2260 KB Output is correct
2 Correct 474 ms 2456 KB Output is correct
3 Correct 477 ms 2236 KB Output is correct
4 Correct 496 ms 2352 KB Output is correct
5 Correct 507 ms 2264 KB Output is correct
6 Correct 461 ms 2300 KB Output is correct
7 Correct 466 ms 2332 KB Output is correct
8 Correct 471 ms 2376 KB Output is correct
9 Correct 471 ms 2316 KB Output is correct
10 Correct 485 ms 2212 KB Output is correct
11 Correct 481 ms 2320 KB Output is correct
12 Correct 495 ms 2240 KB Output is correct
13 Correct 513 ms 2420 KB Output is correct
14 Correct 498 ms 2220 KB Output is correct
15 Correct 549 ms 2208 KB Output is correct
16 Correct 85 ms 2252 KB Output is correct
17 Correct 92 ms 2252 KB Output is correct
18 Correct 88 ms 2224 KB Output is correct
19 Correct 89 ms 2188 KB Output is correct
20 Correct 98 ms 2284 KB Output is correct
21 Incorrect 428 ms 2244 KB Output isn't correct
22 Halted 0 ms 0 KB -