Submission #113647

#	Time	Username	Problem	Language	Result	Execution time	Memory
113647		Mercenary	Boat (APIO16_boat)	C++14	0 / 100	7 ms	384 KiB

boat

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
int Pow(int a , int b){
    if(b == 0)return 1;
    int r = Pow(a , b / 2);
    if(b & 1)return (ll)r * r % mod * a % mod;
    return (ll)r * r % mod;
}
const int div6 = Pow(6,mod-2);
const int div2 = Pow(2,mod-2);
int dp[2][maxn];
vector<int> v;
int n , a[maxn] , b[maxn];

int cal(int dis){
    return ((ll)(dis + 1) * (dis + 1) % mod * dis % mod * div2 % mod -
            (ll)dis * (dis + 1) % mod * (2 * dis + 1) % mod * div6 % mod + mod) % mod;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 0 ; i < n ; ++i){
        cin >> a[i] >> b[i];
        v.pb(a[i]);v.pb(b[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    v.pb(v.back() + 1);
    bool bit = 0;
    for(int i = 0 ; i < n ; ++i){
        bit ^= 1;
        int from = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
        int to = lower_bound(v.begin(),v.end(),b[i]) - v.begin();
        int now = 1;
        for(int j = 0 ; j < v.size() ; ++j){
            if(j)now = (now + (ll)cal(v[j] - v[j - 1]) * dp[bit ^ 1][j - 1] % mod) % mod;
            if(from <= j && j <= to)dp[bit][j] = (dp[bit ^ 1][j] + now) % mod;
            else dp[bit][j] = dp[bit ^ 1][j];
//            cout << i << " " << v[j] << " " << dp[bit][j] << endl;
        }
    }
    int now = 0;
    for(int j = 0 ; j < (int)v.size() ; ++j){
        if(j)now = (now + (ll)cal(v[j] - v[j - 1]) * dp[bit][j - 1] % mod) % mod;
    }
    cout << now;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:55:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0 ; j < v.size() ; ++j){
                         ~~^~~~~~~~~~
boat.cpp:38:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:39:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42