Submission #25545

#	Time	Username	Problem	Language	Result	Execution time	Memory
25545		kajebiii	Boat (APIO16_boat)	C++14	9 / 100	6 ms	4064 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 5e2 + 10, MAX_C = MAX_N * 2, MOD = 1e9 + 7;

int N, Nr[MAX_N][2], Dy[MAX_N][MAX_C], Sum[MAX_C];
vector<int> Co;
int main() {
	cin >> N; 
	REPO(i, N) REP(j, 2) scanf("%d", &Nr[i][j]), Nr[i][j] += j, Co.push_back(Nr[i][j]);
	Co.push_back(0);
	sort(ALL(Co)); Co.erase(unique(ALL(Co)), Co.end());
	REPO(i, N) REP(j, 2) Nr[i][j] = lower_bound(ALL(Co), Nr[i][j]) - Co.begin();

	int cN = SZ(Co);
	Dy[0][0] = 1;
	REPO(i, N) {
		for(int j=0; j+1<cN; j++) {
			if(j) Sum[j] = Sum[j-1]; else Sum[j] = 0;
			Sum[j] = (Sum[j] + Dy[i-1][j]) % MOD;
		}
		for(int j=0; j<cN; j++) Dy[i][j] = Dy[i-1][j];
		for(int j=Nr[i][0]; j<Nr[i][1]; j++)
			Dy[i][j] = (Dy[i][j] + 1ll * Sum[j-1] * (Co[j+1] - Co[j]) ) % MOD;
	}
	int ans = 0;
	for(int j=0; j<cN; j++) ans = (ans + Dy[N][j]) % MOD;
	ans = (ans + MOD - 1) % MOD;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:22:84: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REPO(i, N) REP(j, 2) scanf("%d", &Nr[i][j]), Nr[i][j] += j, Co.push_back(Nr[i][j]);
                                                                                    ^

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