Skip to content

Instantly share code, notes, and snippets.

@vstrimaitis
Created October 29, 2017 19:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vstrimaitis/749456203addd3342557be2c0ae813a7 to your computer and use it in GitHub Desktop.
Save vstrimaitis/749456203addd3342557be2c0ae813a7 to your computer and use it in GitHub Desktop.
OC 2017-10-29
#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;
}
#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;
}
#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