akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define v vector
using namespace std;
typedef long long ll;
v<bool> searched;
v<ll> b; 
v<v<int>> graph;
v<ll> ans;
void dfs(ll, int);
int main(){
    int n, q;
    cin >> n >> q;
    graph.resize(n);
    b.resize(n);
    searched.resize(n);
    ans.resize(n);
    for(int i = 0; i < n - 1; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a - 1].push_back(b - 1);
        graph[b - 1].push_back(a - 1);
    }
    for(int i = 0; i < q; i++){
        ll x, y;
        scanf("%lld %lld", &x, &y);
        b[x - 1] += y;
    }
    dfs(0, 0);
    for(int i = 0; i < n; i++){
        printf("%lld ", ans[i]);
    }
}
void dfs(ll parent_pnt, int current){
    if(searched[current]) return;
    searched[current] = true;
    ans[current] = parent_pnt + b[current];
    for(int child : graph[current]){
        dfs(ans[current], child);
    }
    return;
}


Measured memory_bytes: 22784
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)      x.begin(), x.end()
#define SIZE(x)     static_cast<i64>(x.size())
#define rep(i,n)    for (i64 i = 0, i ## _limit = (n); i < i ## _limit; ++i)
#define reps(i,s,t) for (i64 i = (s), i ## _limit = (t); i <= i ## _limit; ++i)
#define repr(i,s,t) for (i64 i = (s), i ## _limit = (t); i >= i ## _limit; --i)

#ifdef DBG
#define trace(...) _trace(#__VA_ARGS__, __VA_ARGS__);
#else
#define trace(...)
#endif

using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template<class T, class U>inline bool chmax(T &a, const U &b){return b>a && (a=b, true);}
template<class T, class U>inline bool chmin(T &a, const U &b){return b<a && (a=b, true);}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template<class T>
ostream& operator<< (ostream &os, const vector<T> &vec) {
    rep(i, vec.size()) os << vec[i] << (i+1 == vec.size() ? "" : " ");
    return os;
}

template<class T, class U>
ostream& operator<< (ostream &os, const pair<T, U> &p) {
    return os << p.first << ' ' << p.second;
}

template <class T>
void _trace(const char *s, T&& x)
{
    clog << '{';
    while(*s != '\0') clog << *(s++);
    clog << ":" << setw(3) << x << '}' << endl;
}

template <class Head, class... Tail>
void _trace(const char *s, Head&& head, Tail&&... tail)
{
    clog << '{';
    while(*s != ',') clog << *(s++);
    clog << ":" << setw(3) << head << "}, ";
    for (++s; !isgraph(*s); ++s);
    _trace(s, std::forward<Tail>(tail)...);
}
// }}} End Header

int N, C;
int a[32][100010] {};

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> N >> C;

    rep(i, N) {
        int s, t, c;
        cin >> s >> t >> c;
        ++a[c][s];
        --a[c][t+1];
    }

    reps(ch, 1, C) {
        reps(i, 1, 100005) {
            a[ch][i] += a[ch][i-1];
        }
    }

    i64 ans = 0;
    reps(i, 1, 100005) {
        i64 sum = 0;
        reps(ch, 1, C) if (a[ch][i]) ++sum;
        chmax(ans, sum);
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 12160
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
  long N,M;
  cin >> N >> M;
  long l = 1, r = N; 
  
  for (long i = 0; i < M; i++){
    long L,R;
    cin >> L >> R;
    if (l < L) l = L;
    if (r > R) r = R;
  }
  
  long ans = 0;
  for (long i = 1; i <= N; i++){
    if (i >= l && i <= r) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int64_t MOD = 1000000007;
int64_t DP[110][5][5][5]; // i文字目、A,C,G,T,

bool AGC(int a, int b, int c)
{
  return a == 0 && b == 2 && c == 1;
}

bool ACG(int a, int b, int c)
{
  return a == 0 && b == 1 && c == 2;
}

bool GAC(int a, int b, int c)
{
  return a == 2 && b == 0 && c == 1;
}

int main()
{
  int64_t N, ans = 0;
  cin >> N;
  for (int j = 0; j < 4; j++)
  {
    for (int k = 0; k < 4; k++)
    {
      for (int l = 0; l < 4; l++)
      {
        if (AGC(j, k, l) || ACG(j, k, l) || GAC(j, k, l))
          DP[3][j][k][l] = 0;
        else
          DP[3][j][k][l] = 1;
      }
    }
  }
  for (int i = 3; i < N; i++)
  {
    for (int j = 0; j < 4; j++)
    {
      for (int k = 0; k < 4; k++)
      {
        for (int l = 0; l < 4; l++)
        {
          for (int m = 0; m < 4; m++)
          {
            if (AGC(k, l, m) || ACG(k, l, m) || GAC(k, l, m) || AGC(j, k, m) || AGC(j, l, m))
              continue;
            DP[i + 1][k][l][m] = (DP[i + 1][k][l][m] + DP[i][j][k][l]) % MOD;
          }
        }
      }
    }
  }
  for (int j = 0; j < 4; j++)
  {
    for (int k = 0; k < 4; k++)
    {
      for (int l = 0; l < 4; l++)
      {
        ans = (ans + DP[N][j][k][l]) % MOD;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;

int main(){
    long long s,c;
    cin>>s>>c;
    long long ans; 
    if(s*2 > c){
        ans = c / 2;
    }
    else{
        ans = (s + c / 2) / 2;
    }

    cout<<ans<<endl;

    
}

Measured memory_bytes: 256
s=input()
p=s[0]
c1=1
c2=0
q=""
t=1


for i in range(1,4):
    if s[i]==p:
        c1+=1
    else:
        if c2==0:
            c2=1
            q=s[i]
        elif s[i]==q:
            c2+=1
        
if c1==2 and c2==2:
    print("Yes")
else:
    print("No")
    
        



Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define ll long long


int main(){
  ll a,b,c,d;cin >> a >> b >> c >> d;
  // a = 1;b = 1e18 の場合を考える
  // c,d で割り切れる数を数えて引く
  ll ac = (a-1) / c; ll bc = b /c;
  ll ad = (a-1) / d; ll bd = b / d;
  ll gcd = __gcd(c,d);
  ll cd = c*d/gcd;
  ll bcd = b/cd;
  ll acd = (a-1)/cd;
  ll t = (bc + bd - bcd) - (ac + ad - acd);
  ll ans = b - a + 1 - t;
  cout <<ans<< endl;
} 

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

const int INF = 1 << 29;

int main(void)
{
	int route[101][101][2];
	int n, m, q;
	int i, j, k;

	while (scanf("%d %d", &n, &m), n){
		for (i = 1; i <= m; i++){
			for (j = 1; j <= m; j++){
				route[i][j][0] = route[i][j][1] = INF;
			}
		}
		for (i = 0; i < n; i++){
			int from, to, cost, times;
			scanf("%d %d %d %d", &from, &to, &cost, &times);

			route[from][to][0] = route[to][from][0] = fmin(route[from][to][0], cost);
			route[from][to][1] = route[to][from][1] = fmin(route[from][to][1], times);
		}
		for (i = 1; i <= m; i++){
			route[i][i][0] = route[i][i][1] = 0;
		}

		for (i = 1; i <= m; i++){
			for (j = 1; j <= m; j++){
				for (k = 1; k <= m; k++){
					route[j][k][0] = fmin(route[j][k][0], route[j][i][0] + route[i][k][0]);
					route[j][k][1] = fmin(route[j][k][1], route[j][i][1] + route[i][k][1]);
				}
			}
		}

		scanf("%d", &q);
		for (i = 0; i < q; i++){
			int from, to, order;
			scanf("%d %d %d", &from, &to, &order);

			printf("%d\n", route[from][to][order]);
		}
	}

	return (0);
}

Measured memory_bytes: 684
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			
			if (n == 0 && m == 0) {
				break;
			}
			
			int a[] = new int[n];
			int an = 0;
			int answer = 0;
			int a_min = 1000001;
			int a_second_min = 1000001;
			for (int i = 0; i < n; i++) {
				an = sc.nextInt();
				a[i] = an;
				if (an < a_min) {
					a_second_min = a_min;
					a_min = an;
				} else if (an < a_second_min) {
					a_second_min = an;
				}
				
				for (int j = 0; j < i; j++) {
					if ((a[j] + an) > answer && (a[j] + an) <= m) {
						answer = a[j] + an;
					}
				}
			}
			
//			System.out.println(a_min);
//			System.out.println(a_second_min);
//			
			if ((a_min + a_second_min) > m) {
				System.out.println("NONE");
			} else {
				System.out.println(answer);
			}
			
			
		}
	}
}

Measured memory_bytes: 50204
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
#include <set>
using namespace std;

long long sum;
long long maxv=-2000000;
long long minv=2000000;

int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        long long a;cin>>a;
        sum+=a;
        maxv=max(maxv,a);
        minv=min(minv,a);
    }
    cout<<minv<<" "<<maxv<<" "<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3096
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include<set>
#include<queue>
#include <iomanip>

typedef long long ll;

#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[20][20];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}

ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}
ll dp[20500];
int main() {
	string t;
	cin >> s >> t;
	n = s.size();
	if (s == t) {
		cout << "Yes" << endl;
		return 0;
	}
	else {
		rep(i, n) {
			char tmp = s[n-1];
			s.pop_back();
			string p = "";
			p += tmp;
			p += s;
			s = p;
			if (s == t) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='R' && (i+1)%2==0)
        {
            cout<<"No";
            return 0;
        }
        else if(s[i]=='L' && (i+1)%2!=0)
        {
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes";

}


Measured memory_bytes: 256
N, M = [int(c) for c in input().split()]

shops = []
for _ in range(N):
    ab = [int(c) for c in input().split()]
    shops.append(ab)

cost = 0
bought = 0
s_shops = sorted(shops)

for shop in s_shops:
    buying = 0
    while buying < shop[1]:
        if bought == M:
            break
        cost += shop[0]
        buying += 1
        bought += 1

    if bought == M:
        break

print(cost)

Measured memory_bytes: 22376
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int IMF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LIMF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

template<class T, class S> inline bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S> inline bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}







int main(){
    int A, B; std::cin >> A >> B;
    std::cout << A * B << std::endl;
    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int main() {
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	for (int i = 0; i < tx - sx; i++) {
		cout << "R";
	}
	for (int i = 0; i < ty - sy; i++) {
		cout << "U";
	}
	cout << "R";
	for (int i = 0; i < ty - sy + 1; i++) {
		cout << "D";
	}
	for (int i = 0; i < tx - sx + 1; i++) {
		cout << "L";
	}
	cout << "U";
	for (int i = 0; i < ty - sy; i++) {
		cout << "U";
	}
	for (int i = 0; i < tx - sx; i++) {
		cout << "R";
	}
	cout << "U";
	for (int i = 0; i < tx - sx + 1; i++) {
		cout << "L";
	}
	for (int i = 0; i < ty - sy + 1; i++) {
		cout << "D";
	}
	cout << "R";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long

using namespace std;

typedef pair<int, int> P;

int main(){
	int n, m;
	cin >> n >> m;
	vector<P> py(m);
	vector<vector<int>> yrs(n);
	REP(i, m){
		cin >> py[i].first >> py[i].second;
		yrs[py[i].first-1].push_back(py[i].second);
	}
	REP(i, n){sort(yrs[i].begin(), yrs[i].end());}
	REP(i, m){
		int id = lower_bound(yrs[py[i].first-1].begin(), yrs[py[i].first-1].end(), py[i].second)
				- yrs[py[i].first-1].begin();
		printf("%06d", py[i].first);
		printf("%06d\n", id+1);
	}
}


Measured memory_bytes: 7808
use std::io::*;
use std::collections::{ HashMap, HashSet };

fn read(s: &mut StdinLock) -> u64 {
    s.by_ref().bytes().map(|c| c.unwrap() as char)
        .take_while(|c| !c.is_whitespace())
        .skip_while(|c| c.is_whitespace())
        .fold(0, |a, x| (x as u8 - b'0') as u64 + a * 10)
}
fn read_line_split(s: &mut StdinLock, n: u64) -> Vec<u64> {
    (0..n).map(|_| read(s)).collect()
}

fn main() {
    let s = stdin();
    let mut s = s.lock();
    let n: u64 = read(&mut s);
    let a: Vec<u64> = read_line_split(&mut s, n);
    let mut cnt_map: HashMap<u64, u64> = HashMap::new();
    for i in &a {
        *cnt_map.entry(*i).or_insert(0) += 1;
    }
    let total: u64 = cnt_map.iter().fold(0, |acc, x| acc+(x.1*(x.1-1))/2);
    for i in &a {
        let ans: u64 = total + 1 - cnt_map[i];
        println!("{}", ans);
    }
}

Measured memory_bytes: 17176
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define ms multiset
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define FILE ifstream in("board.in");ofstream out("board.out");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); //uid u1(5, 10); u1(rnd);

int main() {
    fast;
    ll a,b; cin>>a>>b;
    vec<ll> m(a);    ll o = 0;
    for(int q=0; q<a; q++){
        cin>>m[q];
        o+=m[q];
    }
    sort(m.begin(), m.end());
    vec<pll> n(b);
    for(int q=0; q<b; q++) cin>>n[q].F>>n[q].S;
    sort(n.begin(), n.end(), [](pll p1, pll p2){return p1.S>p2.S;});
    for(int q=0, w=0; q<a && w<b; w++){
        for(int e=0; q<a && e<n[w].F; e++, q++){
            if(m[q]>=n[w].S) break;
            o+=n[w].S-m[q];
        }
    }
    cout<<o<<endl;
}

Measured memory_bytes: 2560
#include<iostream>
#include<string>

int main(){
    std::string S, T, U;
    std::cin >> S >> T;
    int A, B;
    std::cin >> A >> B;
    std::cin >> U;
    if(U == S){
        A--;
    }else{
        B--;
    }

    std::cout << A << " " << B << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

const ll MXN=100000;
vl G[MXN];
vvl d(2,vl(MXN,INF));

void dfs(ll x,ll v,ll z){
    d[x][v]=z;
    rep(i,G[v].size()){
        if(d[x][G[v][i]]==INF){
            dfs(x,G[v][i],z+1);
        }
    }
}

int main() {
    ll N,u,v;
    cin >> N >> u >> v;
    u--;v--;
    rep(i,N-1){
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    dfs(0,u,0);
    dfs(1,v,0);
    ll D=0;
    rep(i,N){
        if(d[0][i]<d[1][i]){
            D=max(D,d[1][i]);
        }
    }
    cout << D-1 << endl;
}

Measured memory_bytes: 15316
import java.util.Scanner;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        int[] n = new int[3];
        int ans = 0;
        int k = 0, g = 0;
        for (int i = 0; i < 3; i++) {
            n[i] = sc.nextInt();
            if (n[i] % 2 == 0) {
                k++;
            } else {
                g++;
            }
        }
        if (k > 0 && k < 3) {
            ans++;
            if (k < g) {
                for (int i = 0; i < 3; i++) {
                    if (n[i] % 2 == 0) {
                        continue;
                    }
                    n[i]++;
                }
            } else {
                for (int i = 0; i < 3; i++) {
                    if (n[i] % 2 == 0) {
                        n[i]++;
                    }
                }
            }
        }
        Arrays.sort(n);
        System.out.println(ans + (n[2] - n[1]) + (n[1] - n[0]) / 2);
    }
}

Measured memory_bytes: 21972
# -*- coding:utf-8 -*-

def solve():
    H, W = list(map(int, input().split()))

    ans = "#"*(W+2) + "\r\n"
    for h in range(H):
        ans += "#" + input() + "#\r\n"
    ans += "#"*(W+2)
    
    print(ans)

if __name__ == "__main__":
    solve()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl;
// *min_element(c + l, c + r) *max_element(c + l, c + r)
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// struct Edge {
//  l int to, id;
//   Edge(int to, int id): to(to), id(id) {}
// };

int num[200010];

int cnt[2019];

int main() {
    string s;cin>>s;
    reverse(s.begin(),s.end());
    int pre = 0;
    int ten = 1;
    cnt[0]++;
    rep(i,s.size()) {
        num[i] = (pre + (s[i]-'0')*ten)%2019;
        cnt[num[i]]++;
        pre = num[i];   
        ten = ten*10%2019;
    }
    ll ans = 0;
    rep(i,2019) {
        // if(cnt[i]!=0) cout<<i<<" "<<cnt[i]<<endl;
        ans += cnt[i]*(cnt[i]-1)/2;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 4520
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	const int MOD = 1000000007;
	public K()
	{
		//SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		/*var max = 0;
		for (var k = 1; k < 100; k++)
		{
			max = Max(max, k.ToString().Sum(c => c - '0'));
			WriteLine($"max[{k}] = {max} = {Solve(k)}");
		}*/
		WriteLine(Solve(FL));
		//Out.Flush();
	}
	long Solve(long N)
	{
		var S = N.ToString();
		var i = S.Length - 1;
		while (i >= 0 && S[i] == '9') i--;
		if (i < 0) return S.Length * 9;
		if (i == 0) return (S.Length - 1) * 9 + S[0] - '0';
		return (S[0] - '0') - 1 + (S.Length - 1) * 9;
	}
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int h, w;
  while (cin >> h >> w) {
    const int H = 1000 + 5;
    const int W = 1000 + 5;
    char g[H][W];
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        cin >> g[i][j];
      }
    }

    const lli mod = 1e9 + 7;
    static lli dp[H][W];
    fill(&dp[0][0], &dp[H - 1][W - 1] + 1, 0);
    dp[0][0] = 1;

    int di[] = {0, 1};
    int dj[] = {1, 0};
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        for (int d = 0; d < 2; ++d) {
          int ni = i + di[d];
          int nj = j + dj[d];
          unless (0 <= ni && ni < h) continue;
          unless (0 <= nj && nj < w) continue;
          if (g[ni][nj] == '#') continue;
          (dp[ni][nj] += dp[i][j]) %= mod;
        }
      }
    }
    cout << dp[h - 1][w - 1] << endl;
  }
  
  return 0;
}


Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int INF=1e9;
const int MOD=1e9+7;

int main(){
    int R,G,B,N;
    cin >> R >> G >> B >> N;
    int ans=0;
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            int tmp=N-R*i-G*j;
            if(tmp>=0&&tmp%B==0) ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    while (cin >> N >> M, N) {
        vector<int> C(M), x(N);
        for (int i = 0; i < M; ++i) cin >> C[i];
        for (int i = 0; i < N; ++i) cin >> x[i];
        const int INF = 1 << 30;
        vector<vector<int>> dp(N + 1, vector<int>(256, INF));
        dp[0][128] = 0;
        for (int i = 0; i < N; ++i) for (int j = 0; j < 256; ++j) if (dp[i][j] != INF) {
            for (int k = 0; k < M; ++k) {
                int nj = max(0, min(255, j + C[k]));
                dp[i + 1][nj] = min(dp[i + 1][nj], dp[i][j] + (nj - x[i]) * (nj - x[i]));
            }
        }
        int ans = INF;
        for (int i = 0; i < 256; ++i) {
            ans = min(ans, dp[N][i]);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 23808
#include <bits/stdc++.h>

using namespace std;

int main(){

    string s;
    cin>>s;

    for(auto &it:s){

        if(it=='A')
            cout<<'T';
        if(it=='T')
            cout<<"A";
        if(it=='G')
            cout<<"C";
        if(it=='C')
            cout<<"G";
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> p;
int n;
int m;
vector<int>g[200001];
int dist[200001];
const int INF = 1e9;
int main() {
  cin >> n >> m;

  for(int i = 0; i < m; i++) {
    int a,b;
    cin >> a >> b;
    a--; b--;

    g[a].push_back(b);
    g[b].push_back(a);
  }

  fill(dist,dist+n,INF);
  priority_queue<p,vector<p>,greater<p> > q;

  q.push(p(-1,0));
  
  dist[0] = 0;

  while(!q.empty()) {
    int u = q.top().second;
    int d = q.top().first;
    q.pop();
    if(dist[u] < d) continue;
    for(int i = 0; i < g[u].size(); i++) {
      int v = g[u][i];
      if(dist[v] > dist[u] + 1) {
	dist[v] = dist[u] + 1;
	q.push(p(1,v));
      }
    }
  }
  if(dist[n-1] <= 2) cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 13936
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N, K;
  cin>>N>>K;
  int num=1;
  for(int i=0;i<N;i++){
    if(num<=K){
      num = num*2;
    }
    else{
      num+=K;
    }
  }
  cout<<num<<endl;
}

Measured memory_bytes: 3612
def nCr(n, r):
    r = min(r, n-r)
    x, y = 1, 1
    for i in range(n, n-r, -1):
        x *= i
    for i in range(2, r+1):
        y *= i
    return x//y

n, a, b = map(int, input().split())
v = sorted(list(map(int, input().split())), reverse = True)
print(sum(v[:a])/a)
if(v[0] != v[a-1]):
    print(nCr(v.count(v[a-1]), v[:a].count(v[a-1])))
else:
    c = v.count(v[0])
    m = min(b, c)
    ans = 0
    for i in range(a, m+1):
        ans += nCr(c, i)
    print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,a[MAXN];
ll tot,cnt[MAXN],v1[MAXN],v2[MAXN];
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
		cnt[a[i]]++;
	for(int i=1;i<=n;i++)
	{
		ll num=cnt[i];
		if (num==0)
			continue;
		v1[i]=num*(num-1)/2;
		num--;
		v2[i]=num*(num-1)/2;
		tot+=v1[i];
	}
	for(int i=0;i<n;i++)
	{
		ll ans=tot-v1[a[i]]+v2[a[i]];
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 7040
diagram = gets.chomp.chars

upper_skip = ->{
  loop do
    a = diagram[0]
    return false if a == "\\"
    return true unless a
    diagram.shift
  end
}

downer_skip = ->(target_height) {
  height = index = 0
  until height == target_height
    height -= 1 if diagram.shift == "\\"
    index += 1
  end
  index
}

highest = ->{
  max_index = height = 0
  max_height = -Float::INFINITY 
  diagram.size.times do |j|
    case diagram[j]
    when "\\"
      height -= 1
    when "/"
      height += 1
      max_height, max_index = height, j if max_height < height
      return [0, j] if height.zero?
    end
  end
  [max_height, max_index]
}

calc = ->(from, to) {
  depth = area = 0
  from.upto(to) do
    case diagram.shift
    when "\\"
      area += depth + 1/2r
      depth += 1
    when "_"
      area += depth
    when "/"
      depth -= 1
      area += depth + 1/2r
    end
  end
  area.to_i
}

pools = []
loop do
  break if upper_skip.()
  height, index = highest.()
  if height == -Float::INFINITY
    break
  else
    first_index = downer_skip.(height)
    pools << calc.(first_index, index)
  end
  break if diagram.size.zero?
end

if pools.empty?
  puts 0
  puts 0
else
  puts pools.inject(&:+)
  puts pools.size.to_s + " " + pools.join(" ")
end


Measured memory_bytes: 8912
#include<bits/stdc++.h>

using namespace std;

inline int read(){
	char ch=getchar();int x=0,f=1;
    while(ch<'0' || ch>'9') {
       if(ch=='-') f=-1;
	  	  ch=getchar();
	}
    while(ch<='9' && ch>='0') {
	   x=x*10+ch-'0';
	   ch=getchar();
	}
    return x*f;
}

int a[1001109];

int cnt;

int f[10101001];

int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans=ans*a;
		}
		b>>=1;
		a=a*a;
	}
	return ans;
}

int main(){
	int n=read();
	cnt++;
	a[cnt]=1;
	for(int i=1;i<=n;i++){
		if(ksm(6,i)>n) break;
		cnt++;
		a[cnt]=ksm(6,i);
	}
	for(int i=1;i<=n;i++){
		if(ksm(9,i)>n) break;
		cnt++;
		a[cnt]=ksm(9,i);
	}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=cnt;i++){
		for(int j=a[i];j<=n;j++){
			f[j]=min(f[j],f[j-a[i]]+1);
		}
	}
	cout<<f[n];
	return 0;
}


Measured memory_bytes: 41216
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) {
    
    new Main().run();
  }

  private void run() {

    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int heapSize = Integer.parseInt(br.readLine());
      String[] keys = br.readLine().split(" ");
      int[] mHeap = new int[heapSize+1];
      mHeap[0] = heapSize;
      for(int i=1; i<=heapSize; i++)
        mHeap[i] = Integer.parseInt( keys[i-1] );

      buildMaxHeap(mHeap);

      StringBuilder buf = new StringBuilder();
      for(int i=1; i<mHeap.length; i++) 
        buf.append(" ").append(mHeap[i]);

      System.out.println(buf);
    } catch(IOException e) {
      System.out.println("IOException!");
    }
  }
  private void buildMaxHeap(int[] heap) {
    for(int i= heap[0]/2; i>0; i--)
      maxHeapify(heap, i);
  }
  private void maxHeapify(int[] heap, int node) {
    int t,left,right,largest;
    left  = nodeLeft(node);
    right = nodeRight(node);

    if( (left <= heap[0]) && (heap[left] > heap[node]) )
      largest = left;
    else
      largest = node;
    if( (right <= heap[0]) && (heap[right] > heap[largest]) )
      largest = right;

    if( largest != node ) {
      t = heap[node]; heap[node] = heap[largest]; heap[largest] = t;

      maxHeapify(heap, largest);
    }
  }
  private int nodeLeft(int node) {
    return node*2;
  }
  private int nodeRight(int node) {
    return node*2+1;
  }
}


Measured memory_bytes: 74976
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
using namespace std;
typedef long long ll;

int N,M;
int L[100000],R[100000];

int main(){
    cin>>N>>M;
    rep(i,M) cin>>L[i]>>R[i];

    int l=0,r=100100;
    rep(i,M){
        if(l<L[i]) l=L[i];
        if(R[i]<r) r=R[i];

        if(r-l<0){
            cout<<0<<endl;
            return 0;
        }
    }
    int ans=r-l+1;

    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
void init_fact(){
    kaijo[0]=1;
    for(int i=1;i<=2000000;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
int comb(int a,int b){
    if(!kaijo[0])init_fact();
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
int n,k,q,a[2010],ans=INF;
void func(int Y){
    vector<int>v;
    int le=0,ri=0;
    while(ri<n){
        if(a[ri]<Y){
            if(ri-le>=k){
                vector<int>u;
                for(int j=le;j<ri;j++){
                    u.pb(a[j]);
                }
                sort(all(u));
                rep(i,u.size()-k+1)v.pb(u[i]);
            }
            le=ri+1;
        }
        ri++;
    }
    if(ri-le>=k){
                vector<int>u;
                for(int j=le;j<ri;j++){
                    u.pb(a[j]);
                }
                sort(all(u));
                rep(i,u.size()-k+1)v.pb(u[i]);
    }
    /*for(int i:v)cout<<i<<" ";
    cout<<endl;*/
    sort(all(v));
    if(v.size()<q)return;
    int X=v[q-1];
    chmin(ans,X-Y);
    //cout<<X-Y<<endl;
}
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>k>>q;
    rep(i,n)cin>>a[i];
    rep(i,n){
        func(a[i]);
    }
    cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 100;

int n, a[N];
bool ans, b[N];

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n, greater<int>());
	for (int i = n - 2; ~i; i--)
		b[i] = (a[i] == a[i + 1]? !b[i + 1]: false);
	for (int i = 0; i < n; i++)
		if (i + 1 == a[i]) {
			ans = b[i];
			break;
		}
		else if (a[i] != a[i + 1] && i + 1 >= a[i + 1]) { // i == n - 1 :: ok
			ans = (b[i] ^ ((a[i] - i - 1) & 1));
			if (i + 1 == a[i + 1] && i != n - 1)
				ans |= (!b[i + 1]);
			break;
		}
	cout << (ans? "First": "Second");
}

Measured memory_bytes: 768
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf 1000000000000000000

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int x,y;
    cin>>x>>y;
    int tx=-x,ty=-y;
    int ans=inf;
    if(y>=x)ans=y-x;
    if(ty>=x)ans=min(ans,ty-x+1);
    if(y>=tx)ans=min(ans,y-tx+1);
    if(ty>=tx)ans=min(ans,ty-tx+2);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    long long n;cin>>n;
    long long ans=0;
    for(long long l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        //for(int k=l;k<=r;k++)
        //cout<<k<<" "<<l<<" "<<r<<endl;
        if(l!=r){
            if(!(n%r)) ans+=r-1;
        }
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    int N, K;
    cin >> N >> K;
    vector<int> height(N);
    int num = 0;
    for (int i = 0; i < N; i++) {
        cin >> height.at(i);
        if (height.at(i) >= K) {
            num += 1;
        }
    }

    cout << num << endl;

    return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>
int main(void)
{
	char s[20];
	int k,i; 
	scanf("%s",s);
	k=strlen(s);
	s[5]=' ';
	s[13]=' ';
	printf("%s\n",s);
	return 0;
}
	

Measured memory_bytes: 128
#include<iostream>
#include<vector>
using namespace std;

int main(){
    for(int i = 0; i < 10; i++) cout << "+";
    cout << "[";
    for(int i = 3; i <= 12; i++){
        cout << ">";
        for(int j = 0; j < i; j++)  cout << "+";
    }
    for(int i = 3; i <= 12; i++)    cout << "<";
    cout << "-]>";

    vector<int> v(15, 0);
    for(int i = 3; i <= 12; i++){
        v[i] = i*10;
    }
    int pos = 3;
    
    string s;
    cin >> s;
    for(char c : s){
        int x = (int)c;
        while(pos+1 <= x/10)    cout << ">", pos++;
        while(pos-1 >= x/10)    cout << "<", pos--;
        while(v[pos]+1 <= x)    cout << "+", v[pos]++;
        while(v[pos]-1 >= x)    cout << "-", v[pos]--;
        cout << ".";
    }
    return 0;
}



Measured memory_bytes: 3220
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(n)]
flag = [True for i in range(m+1)]
ans = n
for _ in range(m-1):
    cnt = [0 for i in range(m+1)]
    for i in range(n):
        for j in range(m):
            if flag[a[i][j]]:
                cnt[a[i][j]]+=1
                break
    t = 0
    cat = 0
    for i in range(m+1):
        if cnt[i]>t:
            cat = i
            t = cnt[i]
    ans = min(ans,t)
    flag[cat] = False
print(ans)

Measured memory_bytes: 43612
W, H, N = [int(i) for i in input().split(" ")]

a1 = [0,0]
a2 = [W,0]
a3 = [0,0]
a4 = [0,H]

for i in range(0,N):
  lst = [int(i) for i in input().split(" ")]
  if lst[2] == 1 and lst[0] > a1[0]:
    a1[0] = lst[0]
  elif lst[2] == 2 and lst[0] < a2[0]:
    a2[0] = lst[0]
  elif lst[2] == 3 and lst[1] > a3[1]:
    a3[1] = lst[1]
  elif lst[2] == 4 and lst[1] < a4[1]:
    a4[1] = lst[1]

if (a2[0]-a1[0])<0 or (a4[1]-a3[1])<0:
    print(0)
else:
    print((a2[0]-a1[0])*(a4[1]-a3[1]))

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String... args) {
		// 入力
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();

		int result;

		if (b % a == 0)
			result = a + b;
		else
			result = b - a;

		// 出力
		System.out.println(result);
	}
}

Measured memory_bytes: 21716
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    while (n != 0) {
            
        vector<int> w(n);
        rep(i, n) cin >> w[i];
        // dp[i][j] : iからj-1までのブロックから取れる最大値
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        for (int k = 2; k <= n; k++) {
            for (int i = 0; i + k <= n; i++) {
                if (dp[i + 1][i + k - 1] == k - 2 && abs(w[i] - w[i + k - 1]) < 2) {
                    dp[i][i + k] = k;
                }
                for (int j = i; j <= i + k; j++) {
                    dp[i][i + k] = max(dp[i][i + k], dp[i][j] + dp[j][i + k]);
                }
            }
        }
        cout << dp[0][n] << "\n";
        cin >> n;
    }
}


Measured memory_bytes: 3288
n,p = map(int,input().split())
r = []
for i in range(2,p):
  if i*i > p:
    break
  if p % i != 0:
    continue
  e = 0
  while p%i == 0:
    e += 1
    p //= i
  r.append((i,e))
if n:
  r.append((p,1))
ans = 1
for p,e in r:
  
  ans *= pow(p,e//n)
print(ans)

Measured memory_bytes: 9044
from collections import deque

def bfs(start, maze, H, W):
    max_step = 0
    used = [[False for _ in range(W)] for _ in range(H)]
    start_x, start_y = start
    used[start_x][start_y] = True
    stack = deque([[start, 0]])
    while stack:
        (i, j), step = stack.popleft()
        if maze[i][j] == '#':
            continue
        max_step = max(max_step, step)
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= x < H and 0 <= y < W and not used[x][y]:
                stack.append([(x, y), step + 1])
                used[x][y] = True
    return max_step

if __name__ == '__main__':
    H, W = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(input()))
    ret = 0
    for i in range(H):
        for j in range(W):
            ret = max(ret, bfs((i, j), S, H, W))
    print(ret)

Measured memory_bytes: 46060
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long int64;
typedef pair<int,int> pii;
typedef vector<int> vi;

const double eps = 1e-9;
const int oo = 0x3f3f3f3f;
const int mod = 1000000007;

struct Magic{
    vector<int> v;
    int delta;
    int b, e;

    Magic() {
        v = vi();
        delta = b = e = 0;
    }

    void append(int x){
        x -= delta;

        if (e == v.size())
            v.push_back(0);

        v[e++] = x;
    }

    int front(){
        return v[b] + delta;
    }

    int back(){
        return v[e - 1] + delta;
    }

    void pop_front(){
        b++;
    }

    bool empty(){
        return e == b;
    }

    void pop_back(){
        e--;
    }

    void sub(){
        delta--;

        if (!empty() && front() == 0)
            pop_front();
    }

    bool winner(){
        return front() & 1;
    }

    void enumerate(){
        for (int i = b; i < e; ++i)
            cout << v[i] + delta << " ";
        cout << endl;
    }

    void fix(){
        if (e - b >= 2 && v[e - 1] - 1 == v[e - 2]){
            pop_back();
        }
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;

    vector<int> v(n);

    for (int i = 0; i < n; ++i){
        cin >> v[i];
    }

    sort(v.begin(), v.end());

    Magic ds;

    ds.append(1);

    for (auto u : v){
        u++;
        ds.sub();
        ds.append(u);
        ds.fix();
    }

    cout << (ds.winner() ? "First" : "Second") << endl;

    return 0;
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
using namespace std;
#define ll        long long
#define  sci(x)   scanf("%d", &x)
#define  scl(x)   scanf("%lld", &x)
#define  scd(x)   scanf("%lf", &x)
#define l0(i,n)   for(ll i=0; i<n; i++)
 
int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	//CODE TONOY
	int a[10]={0};
    int n,k;
    int ans = 0;
    int flag = 0;
    int x;
    scanf("%d %d",&n,&k);
    for(int i=0;i<k;i++)
    {
        scanf("%d",&x);
        a[x]++;
    }

    for(int i=n;i<1000069;i++)
    {
        int t = i;
        flag = 0;
        while(t)
        {
            int p = t%10;
            if(a[p]!=0)
            {
                flag = 1;
                break;
            }
            t/=10;
        }
        if(flag==1)
            continue;
        else
        {
             ans = i;
             break;
        }
        //printf("%d ",i);
    }
    printf("%d",ans);
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

# 正負が混在するか判定
plus = False
minus = False
for a in A:
    if a > 0:
        plus = True
    elif a < 0:
        minus = True

ans = []

# 正負が混在する場合、符号を揃える
if plus == True and minus == True:
    max_a = max(A)
    min_a = min(A)
    max_idx = A.index(max_a)
    min_idx = A.index(min_a)
    # 正に揃える
    if abs(max_a) >= abs(min_a):
        for i in range(N):
            A[i] += max_a
            ans.append([max_idx + 1, i + 1])
    # 負に揃える
    if abs(max_a) < abs(min_a):
        for i in range(N):
            A[i] += min_a
            ans.append([min_idx + 1, i + 1])
# print(A)

# 正に揃っている場合
if min(A) >= 0:
    # 前から累積和
    for i in range(1, N):
        A[i] += A[i - 1]
        ans.append([i, i + 1])
# 負に揃っている場合
else:
    # 後ろから累積和
    for i in range(N - 2, -1, -1):
        A[i] += A[i + 1]
        ans.append([i + 2, i + 1])

print(len(ans))
for a in ans:
    print(*a)
# print(A)


Measured memory_bytes: 62664
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v,d])
        self.e[v].append([u,d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s, t):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            if u == t:
                return d[t]
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return None


def main():
    n,m = LI()
    dk = Dijkstra()
    t = []
    r = 0
    for _ in range(m):
        a,b,c = LI()
        dk.add(a,b,c)
        t.append([a,b,c])
    for a,b,c in t:
        d = dk.search(a,b)
        if d < c:
            r += 1
    return r


print(main())


Measured memory_bytes: 6224
n=int(input())
t,a=[int(i) for i in input().split()]

h_list=[int(i) for i in input().split()]

#絶対値のリスト
abs_list=[]
for i in range(n):
    abs_list.append(abs(a-(t-h_list[i]*0.006)))
    
print(abs_list.index(min(abs_list))+1)


Measured memory_bytes: 9160
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<cmath>
#include<queue>	
#include<functional>
#include<climits>
#include<tuple>
#include<utility>

using namespace std;

//define
#define ALL(a) a.begin(),a.end()
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define debug(x) if(1)cout<<#x<<":"<<x<<endl;
#define DEBUG(x) if(1)cout<<#x<<":"<<x<<endl;
#define ll long long
#define pb push_back
#define PB push_back
#define lb lower_bound
#define LB lower_bound
#define ub upper_bound
#define UB upper_bound


//constant
const int MOD = 1000000007;
const int INF = INT_MAX / 2-1;
const double EPS = 1e-9;
const int dx4[4] = { 1,0,-1,0 };
const int dy4[4] = { 0,1,0,-1 };

//typedef
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;


int main() {
	string s;
	cin >> s;
	int a = -1, b = -1;
	REP(i, s.size()) {
		bool isOk = true;
		if (i + 1 < s.size())
			if (s[i] == s[i + 1])
				isOk = false;
		if (i + 2 < s.size())
			if (s[i] == s[i + 2])
				isOk = false;
		if (!isOk) {
			a = i+1;
			if (i + 2 < s.size())
				b = i + 3;
			else
				b = i + 2;
			break;

		}
	}

	cout << a << " " << b << endl;
	
	return 0;
}

Measured memory_bytes: 512
INF = 10 ** 9 + 1

N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())

    line = list(map(int, input().split()))
    s = 0
    for c in line:
        c -= 1
        s |= 1<<c
    key.append((s, a))

dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for state, val in key:
        t = s | state
        cost = dp[s] + val
        dp[t] = min(dp[t], cost)


ans = dp[-1]
if ans == INF:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;

bool FLG = false;

bool kaibun(string s) {
	for (int i = 0; i < s.length(); i++) {
		if (s.at(i) == s.at(s.length() - 1 - i)) {
			FLG = true;
		} else {
			FLG = false;
			break;
		}
	}
	return FLG;
}

int main() {
	string s;
	cin >> s;
	string s_front = s.substr(0, (s.length() - 1) / 2);
	string s_back = s.substr((s.length() + 2) / 2, s.length());

	if (kaibun(s) && kaibun(s_front) && kaibun(s_back)) {
		cout << "Yes" << endl;
	} else{
		cout << "No" << endl;
	}

}


Measured memory_bytes: 256