Created
October 29, 2017 19:24
-
-
Save vstrimaitis/749456203addd3342557be2c0ae813a7 to your computer and use it in GitHub Desktop.
OC 2017-10-29
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#define _CRT_SECURE_NO_WARNINGS | |
#include <iostream> | |
#include <iomanip> | |
#include <fstream> | |
#include <stdio.h> | |
#include <cstdio> | |
#include <stdlib.h> | |
#include <cstdlib> | |
#include <algorithm> | |
#include <cstring> | |
#include <string> | |
#include <vector> | |
#include <list> | |
#include <stack> | |
#include <climits> | |
#include <set> | |
#include <bitset> | |
#include <math.h> | |
#include <queue> | |
#include <map> | |
#include <sstream> | |
#include <functional> | |
#include <assert.h> | |
#include <unordered_map> | |
#include <unordered_set> | |
#include <complex> | |
typedef long long ll; | |
typedef unsigned long long ull; | |
typedef long double ld; | |
typedef std::pair<int, int> pii; | |
typedef std::pair<double, double> pdd; | |
template <typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>; | |
template <typename T> using max_heap = std::priority_queue<T, std::vector<T>, std::less<T>>; | |
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); | |
#define TESTS(t) int NUMBER_OF_TESTS; cin >> NUMBER_OF_TESTS; for(int t = 1; t <= NUMBER_OF_TESTS; t++) | |
#define FOR(i, start, end) for(int i = (start); i < (end); i++) | |
#define ROF(i, start, end) for(int i = (start); i >= (end); i--) | |
#define all(x) (x).begin(), (x).end() | |
//#define endl "\n" | |
#define PI (asin(1)*2) | |
#define OO ((1LL<<31)-1) | |
#define eps 1e-12 | |
#define in(a, b) ((b).find(a) != (b).end()) | |
#define mp(a, b) make_pair((a), (b)) | |
#define sgn(a) ((a) > eps ? 1 : ((a) < -eps ? -1 : 0)) | |
#define cl1(x) ((x)&((x)-1)) // clear lowest 1 bit | |
#define cl0(x) ((x)|((x)+1)) // clear lowest 0 bit | |
#define ct1(x) ((x)&((x)+1)) // clear all trailing 1 bits | |
#define pb push_back | |
#define MOD 1000000007 | |
#define MAX_N 1000 | |
using namespace std; | |
int cnts[10]; | |
void addCnts(int n) { | |
while (n > 0) { | |
cnts[n % 10]++; | |
n /= 10; | |
} | |
} | |
int getFreq() { | |
int best = 0, ans = -1; | |
FOR(i, 0, 10) { | |
if (cnts[i] >= best) { | |
best = cnts[i]; ans = i; | |
} | |
} | |
return ans; | |
} | |
bool startsWith9(string s) { | |
FOR(i, 0, s.length() - 1) { | |
if (s[i] != '9') return false; | |
} | |
return true; | |
} | |
bool endWith9s(string s) { | |
FOR(i, 1, s.length()) { | |
if (s[i] != '9') return false; | |
} | |
return true; | |
} | |
pii getLastNotNine(string s) { | |
ROF(i, s.length() - 1, 0) { | |
if (s[i] == '9') continue; | |
if (s[i] == '0') return { 10, -1 }; | |
int ans = s[i] - '0'; | |
return { ans, i }; | |
} | |
} | |
int main() | |
{ | |
FAST_IO | |
#ifdef _DEBUG | |
freopen("input.txt", "r", stdin); | |
freopen("output.txt", "w", stdout); | |
#endif | |
/*FOR(i, 1, 1000000) { | |
addCnts(i); | |
ostringstream ss; | |
ss << i; | |
string s = ss.str(); | |
int mx = 10; | |
if (startsWith9(s) && s[s.length()-1] != '0') { | |
mx = s[s.length() - 1] - '0'; | |
} | |
else { | |
//mx = s[0] - '0' - 1; | |
int idx = -1; | |
if(s[s.length()-1] == '9') { | |
auto x = getLastNotNine(s); | |
mx = min(mx, x.first); | |
idx = x.second; | |
} | |
if (endWith9s(s)) { | |
mx = min(mx, s[0] - '0'); | |
} | |
else { | |
mx = min(mx, s[0] - '0' - 1); | |
} | |
FOR(i, 1, s.length()) { | |
if (idx != -1 && i == idx) continue; | |
if (s[i] == '0') continue; | |
int curr = s[i] - '0'; | |
if (i != s.length() - 1) curr--; | |
if (s[i] == '1' && i != s.length() - 1) curr++; | |
//else if (i + 1 < s.length() && s[i+1] == '9') curr++; | |
mx = min(mx, curr); | |
} | |
if (mx == 0) mx++; | |
} | |
cout << i << "\t\t\t"; | |
if (mx != getFreq()) { | |
cout << "Expected " << getFreq() << ", got " << mx; | |
} | |
cout << endl; | |
//cout << i << ")" << getFreq() << endl; | |
}*/ | |
string s; | |
cin >> s; | |
int mx = 10; | |
if (startsWith9(s) && s[s.length() - 1] != '0') { | |
mx = s[s.length() - 1] - '0'; | |
} | |
else { | |
//mx = s[0] - '0' - 1; | |
int idx = -1; | |
if (s[s.length() - 1] == '9') { | |
auto x = getLastNotNine(s); | |
mx = min(mx, x.first); | |
idx = x.second; | |
} | |
if (endWith9s(s)) { | |
mx = min(mx, s[0] - '0'); | |
} | |
else { | |
mx = min(mx, s[0] - '0' - 1); | |
} | |
FOR(i, 1, s.length()) { | |
if (idx != -1 && i == idx) continue; | |
if (s[i] == '0') continue; | |
int curr = s[i] - '0'; | |
if (i != s.length() - 1) curr--; | |
if (s[i] == '1' && i != s.length() - 1) curr++; | |
//else if (i + 1 < s.length() && s[i+1] == '9') curr++; | |
mx = min(mx, curr); | |
} | |
if (mx == 0) mx++; | |
} | |
cout << mx << endl; | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#define _CRT_SECURE_NO_WARNINGS | |
#include <iostream> | |
#include <iomanip> | |
#include <fstream> | |
#include <stdio.h> | |
#include <cstdio> | |
#include <stdlib.h> | |
#include <cstdlib> | |
#include <algorithm> | |
#include <cstring> | |
#include <string> | |
#include <vector> | |
#include <list> | |
#include <stack> | |
#include <climits> | |
#include <set> | |
#include <bitset> | |
#include <math.h> | |
#include <queue> | |
#include <map> | |
#include <sstream> | |
#include <functional> | |
#include <assert.h> | |
#include <unordered_map> | |
#include <unordered_set> | |
#include <complex> | |
typedef long long ll; | |
typedef unsigned long long ull; | |
typedef long double ld; | |
typedef std::pair<int, int> pii; | |
typedef std::pair<double, double> pdd; | |
template <typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>; | |
template <typename T> using max_heap = std::priority_queue<T, std::vector<T>, std::less<T>>; | |
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); | |
#define TESTS(t) int NUMBER_OF_TESTS; cin >> NUMBER_OF_TESTS; for(int t = 1; t <= NUMBER_OF_TESTS; t++) | |
#define FOR(i, start, end) for(int i = (start); i < (end); i++) | |
#define ROF(i, start, end) for(int i = (start); i >= (end); i--) | |
#define all(x) (x).begin(), (x).end() | |
//#define endl "\n" | |
#define PI (asin(1)*2) | |
#define OO ((1LL<<31)-1) | |
#define eps 1e-12 | |
#define in(a, b) ((b).find(a) != (b).end()) | |
#define mp(a, b) make_pair((a), (b)) | |
#define sgn(a) ((a) > eps ? 1 : ((a) < -eps ? -1 : 0)) | |
#define cl1(x) ((x)&((x)-1)) // clear lowest 1 bit | |
#define cl0(x) ((x)|((x)+1)) // clear lowest 0 bit | |
#define ct1(x) ((x)&((x)+1)) // clear all trailing 1 bits | |
#define pb push_back | |
#define MOD 1000000007 | |
#define MAX_N 1000 | |
using namespace std; | |
int wins[8][3] = { {0, 1, 2},{ 3,4,5 },{ 6,7,8 },{ 0,3,6 },{ 1,4,7 },{ 2,5,8 },{ 0,4,8 },{ 2,4,6 } }; | |
int board[9]; | |
int getWinner() { | |
FOR(i, 0, 8) { | |
if (board[wins[i][0]] == 0) continue; | |
if (board[wins[i][0]] == board[wins[i][1]] && board[wins[i][1]] == board[wins[i][2]]) | |
return board[wins[i][0]]; | |
} | |
return 0; | |
} | |
bool isFull() { | |
FOR(i, 0, 8) if (board[i] == 0) return false; | |
return true; | |
} | |
int minmax(/*int board[9], */int player) { | |
int win = getWinner(); | |
if (win != 0) return win*player; | |
int move = -1; | |
int score = -2; | |
FOR(i, 0, 9) { | |
if (board[i] == 0) { | |
board[i] = player; | |
int newScore = -minmax(-player); | |
if (newScore > score) { | |
score = newScore; | |
move = i; | |
} | |
board[i] = 0; | |
} | |
} | |
if (move == -1) return 0; | |
return score; | |
} | |
void doMove() { | |
int move = -1; | |
int score = -2; | |
FOR(i, 0, 9) { | |
if (board[i] == 0) { | |
board[i] = 1; | |
int newScore = -minmax(-1); | |
board[i] = 0; | |
if (newScore > score) { | |
score = newScore; | |
move = i; | |
} | |
} | |
} | |
if (move == -1) { | |
exit(0); | |
} | |
board[move] = 1; | |
int r = move / 3 + 1; | |
int c = move - 3*(r-1) + 1; | |
cout << r << " " << c << endl; | |
} | |
void readMove() { | |
int r, c; | |
cin >> r >> c; | |
int x = (r - 1) * 3 + c - 1; | |
board[x] = -1; | |
} | |
void play() { | |
while (true) { | |
doMove(); | |
if (getWinner() != 0 || isFull()) { | |
exit(0); | |
} | |
readMove(); | |
} | |
} | |
int main() | |
{ | |
FAST_IO | |
#ifdef _DEBUG | |
//freopen("input.txt", "r", stdin); | |
//freopen("output.txt", "w", stdout); | |
#endif | |
char c; | |
cin >> c; | |
if (c == 'O') readMove(); | |
play(); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#define _CRT_SECURE_NO_WARNINGS | |
#include <iostream> | |
#include <iomanip> | |
#include <fstream> | |
#include <stdio.h> | |
#include <cstdio> | |
#include <stdlib.h> | |
#include <cstdlib> | |
#include <algorithm> | |
#include <cstring> | |
#include <string> | |
#include <vector> | |
#include <list> | |
#include <stack> | |
#include <climits> | |
#include <set> | |
#include <bitset> | |
#include <math.h> | |
#include <queue> | |
#include <map> | |
#include <sstream> | |
#include <functional> | |
#include <assert.h> | |
#include <unordered_map> | |
#include <unordered_set> | |
#include <complex> | |
typedef long long ll; | |
typedef unsigned long long ull; | |
typedef long double ld; | |
typedef std::pair<int, int> pii; | |
typedef std::pair<double, double> pdd; | |
template <typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>; | |
template <typename T> using max_heap = std::priority_queue<T, std::vector<T>, std::less<T>>; | |
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); | |
#define TESTS(t) int NUMBER_OF_TESTS; cin >> NUMBER_OF_TESTS; for(int t = 1; t <= NUMBER_OF_TESTS; t++) | |
#define FOR(i, start, end) for(int i = (start); i < (end); i++) | |
#define ROF(i, start, end) for(int i = (start); i >= (end); i--) | |
#define all(x) (x).begin(), (x).end() | |
//#define endl "\n" | |
#define PI (asin(1)*2) | |
#define OO ((1LL<<31)-1) | |
#define eps 1e-12 | |
#define in(a, b) ((b).find(a) != (b).end()) | |
#define mp(a, b) make_pair((a), (b)) | |
#define sgn(a) ((a) > eps ? 1 : ((a) < -eps ? -1 : 0)) | |
#define cl1(x) ((x)&((x)-1)) // clear lowest 1 bit | |
#define cl0(x) ((x)|((x)+1)) // clear lowest 0 bit | |
#define ct1(x) ((x)&((x)+1)) // clear all trailing 1 bits | |
#define pb push_back | |
#define MOD 1000000007 | |
#define MAX_N 1000 | |
using namespace std; | |
int toSeconds(string t) { | |
return 3600 * (10*(t[0]-'0') + t[1]-'0') + 60 * (10*(t[3]-'0') + t[4]-'0') + (10*(t[6]-'0') + t[7]-'0'); | |
} | |
vector<pair<int, pii>> pts; // {profit, coordinate, prevCoord} | |
ll bestSoFar[100000]; | |
int main() | |
{ | |
FAST_IO | |
#ifdef _DEBUG | |
freopen("input.txt", "r", stdin); | |
freopen("output.txt", "w", stdout); | |
#endif | |
int n, c; | |
cin >> n >> c; | |
FOR(i, 0, n) { | |
string start, end; | |
int p; | |
cin >> start >> end >> p; | |
int startTime = toSeconds(start); | |
int endTime = toSeconds(end); | |
p -= c*(endTime - startTime); | |
if (p <= 0) continue; | |
//pts.pb({ 0, {startTime, -1} }); | |
pts.pb({ p, {startTime, endTime} }); | |
} | |
sort(pts.begin(), pts.end(), [](pair<int, pii> a, pair<int, pii> b) -> bool { | |
return a.second.second < b.second.second; | |
}); | |
int idx = 0; | |
FOR(i, 1, 86400) { | |
bestSoFar[i] = bestSoFar[i - 1]; | |
while (idx < pts.size() && pts[idx].second.second == i) { | |
ll prev = bestSoFar[pts[idx].second.first]; | |
ll added = prev + pts[idx].first; | |
bestSoFar[i] = max(bestSoFar[i], added); | |
idx++; | |
} | |
} | |
cout << bestSoFar[86399] << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment