第2回早稲田大学プログラミングコンテスト

Submission #4036197

Source codeソースコード

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;
const ll MOD = 1000000007, N = 5000, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };

ll mn(ll a, ll b) {
	if (a == -1)return b;
	if (b == -1)return a;
	return min(a, b);
}
ll gcd(ll v1, ll v2) {
	if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
}
struct ab {
	ll a, b;
	bool operator<(const ab& right) const {
		return right.b*a - right.a*b < 0;
	}
};

/*
void src(ll v, ll d[]) {
priority_queue<pos> q;
q.push(make_pair(0, v));
while (!q.empty()) {
ll ci = q.top().second, cd = -q.top().first;
q.pop();
if (d[ci] != -1)continue; d[ci] = cd;
for (int i = 0; i < G[ci].size(); i++) {
ll ni = G[ci][i].second, nd = cd + G[ci][i].first;
if (d[ni] != -1)continue;
q.push(make_pair(-nd, ni));
}
}
}
*/

ll n, dp[N];
string s;

int main() {
	cin >> n >> s;
	memset(dp, -1, sizeof(dp));
	dp[0] = (s[0] == 'X');
	for (int i = 0; i+1 < s.size(); i++) {
		if (i + 1 < s.size())dp[i + 1] = mn(dp[i + 1], dp[i] + (s[i+1] == 'X'));
		if (i + 2 < s.size())dp[i + 2] = mn(dp[i + 2], dp[i] + (s[i+2] == 'X'));
		if (i + 2 < s.size())dp[i + 2] = mn(dp[i + 2], dp[i] + (s[i+3] == 'X'));
	}
	cout << dp[n - 1] << endl;
	return 0;
}

Submission

Task問題 B - 雨上がり
User nameユーザ名 eric_endo
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1460 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 50 case_000.txt,case_001.txt,case_002.txt,case_003.txt,case_004.txt,case_005.txt,case_006.txt,case_007.txt,case_008.txt,case_009.txt,case_010.txt,case_011.txt,case_012.txt,case_013.txt,case_014.txt,case_015.txt,case_016.txt,case_017.txt,case_018.txt,case_019.txt,case_020.txt,case_021.txt,case_022.txt,case_023.txt,case_024.txt,case_025.txt,case_026.txt,case_027.txt,case_028.txt,case_029.txt,case_030.txt,case_031.txt,case_032.txt,case_033.txt,case_034.txt,case_035.txt,case_036.txt,case_037.txt,case_038.txt,case_039.txt,case_040.txt,case_041.txt,case_042.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
case_000.txt AC 1 ms 256 KB
case_001.txt AC 1 ms 256 KB
case_002.txt AC 1 ms 256 KB
case_003.txt AC 1 ms 256 KB
case_004.txt AC 1 ms 256 KB
case_005.txt AC 1 ms 256 KB
case_006.txt AC 1 ms 256 KB
case_007.txt WA
case_008.txt AC 1 ms 256 KB
case_009.txt AC 1 ms 256 KB
case_010.txt WA
case_011.txt AC 1 ms 256 KB
case_012.txt AC 1 ms 256 KB
case_013.txt WA
case_014.txt WA
case_015.txt AC 1 ms 256 KB
case_016.txt WA
case_017.txt AC 1 ms 256 KB
case_018.txt WA
case_019.txt AC 1 ms 256 KB
case_020.txt WA
case_021.txt AC 1 ms 256 KB
case_022.txt WA
case_023.txt WA
case_024.txt WA
case_025.txt WA
case_026.txt AC 1 ms 256 KB
case_027.txt AC 1 ms 256 KB
case_028.txt AC 1 ms 256 KB
case_029.txt AC 1 ms 256 KB
case_030.txt WA
case_031.txt WA
case_032.txt AC 1 ms 256 KB
case_033.txt AC 1 ms 256 KB
case_034.txt AC 1 ms 256 KB
case_035.txt AC 1 ms 256 KB
case_036.txt WA
case_037.txt AC 1 ms 256 KB
case_038.txt WA
case_039.txt WA
case_040.txt WA
case_041.txt AC 1 ms 256 KB
case_042.txt WA