akhauriyash/Code-Regression huggingface dataset:
L, R = gets.split.map(&:to_i)

target = []
tmp = L
for i in 1..2019
    break if tmp > R 
    target.push(tmp)
    tmp += 1
end

ans = 2020
target.each_with_index{|x,xi|
    target.each_with_index{|y,yi|
        next if xi == yi
        # puts ("x=#{x} xi=#{xi} y=#{y} yi=#{yi}")
        ans = [(x*y)%2019, ans].min
    }
}

puts ans


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




int main() {
  
int W,a,b;
  cin>>W>>a>>b;
  
  if (a<b-W){
    cout<<b-a-W<<endl;
  }
  
  else if (b-W<=a and a<=b+W){
    cout<<0;
  }
  
  else if(a>b+W){
    cout<<a-b-W<<endl;
  }
}










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

int main(){
	int count, a, b, tmp;

	while (cin >> a >> b){
		count = 0;
		tmp = a + b;
		while (tmp > 0){
			count++;
			tmp /= 10;
		}
		cout << count << endl;
	}
	return 0;
}


Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
constexpr int INF = 1e9;
constexpr long long INFLL = 1LL<<60;
constexpr double eps = (1e-9);

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

  ll a, b, x;
  cin >> a >> b >> x;

  ll u = b / x;
  ll l = max(0LL, (a - 1)) / x;
  ll ans = u - l;

  if (a == 0) ans++;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.math.*;
import java.lang.*;

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

class Solution{
	void solve(){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		while(n-- > 0){
			int x = 0, y = 0;
			int X = 0, Y = 0;
			while(true){
				int a = scan.nextInt();
				int b = scan.nextInt();
			
				if(a == 0 && b == 0) break;
				
				x += a;
				y += b;
				
				if(X*X + Y*Y <= x*x + y*y){
					X = x;
					Y = y;
				}
			}
			System.out.println(X + " " + Y);
		}
	}

}

Measured memory_bytes: 32644
#include <iostream>

int mcxi2int(std::string s) {
	int ret = 0;
	int tmp = 1;
	for (int i = 0; i < s.size(); i++) {
		switch (s[i]) {
			default: {
				tmp = s[i] - '0';
				break;
			}
			case 'm': { ret += tmp * 1000, tmp = 1; break; }
			case 'c': { ret += tmp * 100, tmp = 1; break; }
			case 'x': { ret += tmp * 10, tmp = 1; break; }
			case 'i': { ret += tmp * 1, tmp = 1; break; }
		}
	}
	
	return ret;
}

std::string int2mcxi(int n) {
	char s[16];
	int count = 0;
	if (n / 1000 > 0) {
		if (n / 1000 != 1) {
			s[count++] = n / 1000 + '0';
		}
		s[count++] = 'm';
		n -= (n / 1000) * 1000;
	}
	if (n / 100 > 0) {
		if (n / 100 != 1) {
			s[count++] = n / 100 + '0';
		}
		s[count++] = 'c';
		n -= (n / 100) * 100;
	}
	if (n / 10 > 0) {
		if (n / 10 != 1) {
			s[count++] = n / 10 + '0';
		}
		s[count++] = 'x';
		n -= (n / 10) * 10;
	}
	if (n > 0) {
		if (n != 1) {
			s[count++] = n + '0';
		}
		s[count++] = 'i';
	}
	s[count] = '\0';
	
	return s;
}

int main() {
	int n;
	std::cin >> n;

	while (n--) {
		std::string inputs[2];
		std::cin >> inputs[0] >> inputs[1];
		int sum = mcxi2int(inputs[0]) + mcxi2int(inputs[1]);
		std::cout << int2mcxi(sum) << std::endl;
	}
	
	return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int r = scan.nextInt();

        if (r < 1200) {
            System.out.println("ABC");
        } else if (r < 2800) {
            System.out.println("ARC");   
        } else {
            System.out.println("AGC");
        }
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <ctype.h>
#include <string>

using namespace std;

string toUpper(string str) {
    for (int i = 0; i < str.size(); i++) str[i] = toupper(str[i]);
    return str;
}

int main () {
    string w, t;
    int cnt = 0;

    cin >> w;
    w = toUpper(w);
    while (true) {
        cin >> t;
        if (t == "END_OF_TEXT") break;

        t = toUpper(t);
        if (t == w) cnt++;
    }

    cout << cnt << endl;
}


Measured memory_bytes: 3164
// AOJ_C++.cpp : アプリケーションのエントリ ポイントを定義します。
//
#include <iostream>
#include <math.h>

int main()
{
	int a, b;
	std::cin >> a >> b;
	if (a > b) {
		std::cout << "a > b" << std::endl;
	}
	else if (a < b) {
		std::cout << "a < b" << std::endl;
	}
	else if (a == b) {
		std::cout << "a == b" << std::endl;
	}
	else {
		std::cout << "error" << std::endl;
	}
	
    return 0;
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < int(n); i++)
#define FOR(i, a, b) for (int i = a; i < int(b); i++)
#define FOREACH(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define SIZE(v) ((int)(v).size())
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define ll long long
#define llint long long
#define pii pair<int, int>
#define UNVISITED -1

const int MAX = 3030;
ll board[MAX][MAX];
ll dp[MAX][MAX][4];
bool visited[MAX][MAX][4];
int R, C, K; 

ll solve(int r, int c, int k) {
	if(!visited[r][c][k]) {
		visited[r][c][k] = true;
		dp[r][c][k] = 0;
		ll& ans = dp[r][c][k];

		if(r == R && c == C) {
			if(k != 0) {
				dp[r][c][k] = board[r][c];
			}
		}
		else {
			if(r != R) {
				ans = max(ans, solve(r + 1, c, 3));
				if(k != 0) ans = max(ans, solve(r + 1, c, 3) + board[r][c]); 
			}
			if(c != C) {
				ans = max(ans, solve(r, c + 1, k));
				if(k != 0) ans = max(ans, solve(r, c + 1, k - 1) + board[r][c]);
			}
		}
		// printf("%lld\n", ans);
	}
	return dp[r][c][k];
}

int main() {
	scanf("%d %d %d", &R, &C, &K);
	REP(i, K) {
		int r, c;
		ll v; scanf("%d %d %lld", &r, &c, &v);
		board[r][c] = v;
	}
	ll ans = solve(1, 1, 3);
	printf("%lld\n", ans);
}

Measured memory_bytes: 394532
S = input()
T = input()
flag = False
for i in range(len(S)):
    k = len(S) - i - len(T)
    for j in range(len(T)):
        if k >= 0 and (S[k] == T[j] or S[k] == '?'):
            k += 1
            if j == len(T) - 1:
                flag = True
                st = len(S) - len(T) - i
        else:
            break
    if flag:
        break
ret = ""
if flag:
    for i in range(st):
        if S[i] == '?':
            ret += 'a'
        else:
            ret += S[i]
    ret += T
    for i in range(st + len(T), len(S)):
        if S[i] == '?':
            ret += 'a'
        else:
            ret += S[i]
else:
    ret = "UNRESTORABLE"
print(ret)


Measured memory_bytes: 38256
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <set>
#include <numeric>
#include <bitset>
#include <map>
#include <limits.h>

using namespace std;

/// 各桁の和
int sumdigit(int x){
   int sum = 0;
    while(x != 0){
        sum += x % 10;
        x /= 10;
    }
    return sum;
}
/// 最小公倍数 
int gcd(int x, int y){
      if(x<y){
          int temp = x;
          x = y;
          y = temp;
      }
      int r = x % y;
       while(r!=0){
           x = y;
           y = r;
           r = x % y;
       }
      return y;
   }



int main(){
long long K,A,B;
cin >> K >> A >> B;
long long genzai_biskets = 1;
long long mouke_biskets = B - A;
if(B-A <= 2){
    cout << K+1 << endl;
    return 0;
}
else{
    while(1){
        if(K==0){
            cout << genzai_biskets << endl;
            return 0 ;
        }
if (A <=  genzai_biskets){
    if(K >= 2){
        K = K-2;
    genzai_biskets = genzai_biskets + mouke_biskets;
    }
    else{
        cout << genzai_biskets + K << endl;
        return 0;
    }
}
else{
    if(mouke_biskets >= A - genzai_biskets + 2 ){
        if(K >= A - genzai_biskets + 2){
            K = K - (A - genzai_biskets + 2);
            genzai_biskets = B;
        }
        else{
            cout << genzai_biskets  + K << endl;
            return 0;
        }
    }
    else{
        K = K - 1;
        genzai_biskets++;
    }
}

    }
    }
}

Measured memory_bytes: 256
from math import gcd

# segfunc: 問題に応じて設定
def segfunc(x, y):
    return gcd(x, y)


# 配列aで初期化
def init(a):
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2]) 


# a[k]の値をxに更新
def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k - 1) // 2
        seg[k] = segfunc(seg[k*2+1], seg[k*2+2])


# [p, q)についてsegfuncを適用したものを返す
def query(p, q):
    if q <= p:
        return ide_ele
    
    p += num - 1
    q += num - 2
    res = ide_ele

    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(res, segfunc(seg[p], seg[q]))
    
    return res


n = int(input())
a = list(map(int, input().split()))

ide_ele = 0
num = 2 ** (len(bin(n - 1)) - 2)
seg = [ide_ele] * 2 * num
init(a)

res = 0
for i in range(n):
    res = max(res, gcd(query(0, i), query(i+1, n)))

print(res)


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

int N, A;
int a, b, c, d, e, k;
int main(){
    int min = 10, sum = 0;
    int v[10];
    for(int i=0; i<5; i++)
	cin >> v[i];

    for(int i=0; i<5; i++){
	a = v[i] % 10;
	if(min > a && a!= 0)
	    min = a;	
    }
	

    
    for(int i=0; i<5; i++){
	sum += ceil((double)v[i]/10.0) * 10;	
    }
    cout << sum - 10 + min << "\n";
    // if(ans == 1)
    // 	cout << "Yay!" << "\n";
    // else
    // 	cout << ":(" << "\n";

 }




Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
struct Fact{
	vector<long> f;
	vector<long> rf;
	long pow(long N,long K){
		if(K == 0){
			return 1;
		}
		else if(K % 2 == 0){
			long t = pow(N,K/2);
			return t*t%mod;
		}
		else{
			return N*pow(N,K-1)%mod;
		}
	}
	Fact(int N):f(N+1),rf(N+1){
		for(int i=0;i<N+1;i++){
			if(i == 0){
				f[i] = 1;
			}
			else{
				f[i] = (f[i-1]*i)%mod;
			}
		}
		for(int i=N;i>=0;i--){
			if(i == N){
				rf[i] = pow(f[N],mod-2);
			}
			else{
				rf[i] = rf[i+1]*(i+1)%mod;
			}
		}
	}
	long GetFact(int N){
		return f[N];
	}
	long GetPerm(int N,int R){
		return f[N] * rf[N-R] % mod;
	}
	long GetConv(int N,int R){
		return ((f[N]*rf[R])%mod*rf[N-R])%mod;
	}
	long GetRev(int N){
		if(N == 0){
			return 1;
		}
		else{
			return rf[N] * f[N-1] % mod;
		}
	}
};
long PowA[100001];
long PowB[100001];
void Calc(){
	int N = rei();
	int A = rei();
	int B = rei();
	int C = rei();
	Fact F(2*N+1000);
	long pa = A*F.GetRev(A+B) % mod;
	long pb = B*F.GetRev(A+B) % mod;
	long ans = 0;
	PowA[0] = 1;
	PowB[0] = 1;
	for(int i=1;i<=N;i++){
		PowA[i] = PowA[i-1] * pa % mod;
		PowB[i] = PowB[i-1] * pb % mod;
	}
	for(int i=0;i<N;i++){
		long c = F.GetConv(N-1+i,i);
		c *= (PowA[i]*PowB[N] % mod + PowA[N]*PowB[i] % mod) * (N+i) % mod;
		c %= mod;
		ans += c;
	}	
	ans %= mod;
	ans *= 100*F.GetRev(A+B) % mod;
	ans %= mod;
	cout << ans << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 4992
N=int(input())
data=[]
for i in range(1,10**6+1):
    if (N-1)%i==0:
        j=(N-1)//i
        k=i
        if j!=1:
            data.append(j)
        if k!=1:
            data.append(k)

if not data:
    data.append(N-1)
    
data=set(data)
data=list(data)
data=sorted(data)
ans=len(data)
if N==2:
   ans=0


Data=[]

for i in range(1,10**6+1):
    if N%i==0:
        j=N//i
        k=i
        if j!=k:
            Data.append(j)
            Data.append(k)
            
        elif j==k:
            Data.append(j)
if not Data:
    Data.append(N)


Data=sorted(Data)
Data=list(set(Data))

from fractions import gcd
for num in Data:
    ori=N
    if num>1:
        while ori>=num :
            if ori%num==0:
                ori=ori//num
            else:
                ori=ori%num
        if ori==1:
            ans+=1
      

print(ans)
            


    
        
        



Measured memory_bytes: 5676
#include <iostream>
#include <algorithm>

using namespace std;

struct Card
{
    char value;
    char suit;
};

void trace(Card A[], int n)
{
    cout << A[0].suit << A[0].value;
    for(int i=1; i < n; i++)
    {
        cout << " " << A[i].suit << A[i].value;
    }
    cout << endl;

    return;
}

bool isStable(Card C1[], Card C2[], int n)
{
    for(int i = 0; i < n; i++)
    {
        if(C1[i].suit != C2[i].suit)
            return false;
    }

    return true;
}

void bubbleSort(Card C[], int n)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = n-1; j >= i; j--)
        {
            if(C[j].value < C[j-1].value)
                swap(C[j], C[j-1]);
        }
    }

    return;
}

void selectionSort(Card C[], int n)
{
    for(int i = 0; i < n; i++)
    {
        int minj = i;
        for(int j = i; j < n; j++)
        {
            if(C[j].value < C[minj].value)
                minj = j;
        }
        swap(C[i], C[minj]);
    }

    return;
}

int main(void)
{
    int n;
    Card C1[36], C2[36];

    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> C1[i].suit >> C1[i].value;
    
    for(int i = 0; i < n; i++)
        C2[i] = C1[i];

    bubbleSort(C1, n);
    selectionSort(C2, n);

    trace(C1, n);
    cout << "Stable" << endl;

    trace(C2, n);
    if(isStable(C1, C2, n))
        cout << "Stable" << endl;
    else
        cout << "Not stable" << endl;
    
    return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <stdlib.h>
using namespace std;
long long n,m;
long long ans=1;
int main(){
    cin>>n>>m;
    if(abs(n-m)>=2){
        cout<<0;
        return 0;
    }
    if(n==m) ans=2;
    for(int i=1;i<=n;i++){
        ans=(ans*i)%1000000007;
    }for(int i=1;i<=m;i++){
        ans=(ans*i)%1000000007;
    }
    cout<<ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
#define runforestrun ios_base::sync_with_stdio(0)

int main() {
    runforestrun;
    string s;
    cin >> s;
    if(s == "Sunny") cout << "Cloudy";
    else if(s == "Cloudy") cout << "Rainy";
    else cout << "Sunny";
}

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

using namespace std;

int main() {
  string a, b;
  cin >> a >> b;
  
  string sa, sb;
  
  for(int i=0; i<stoi(b); i++){
    sa = sa + a;
  }
  
  for(int i=0; i<stoi(a); i++){
    sb = sb + b;
  }
  
  if(sa <= sb){
    cout << sa << endl;
  } else { 
    cout << sb << endl;
  }
  return 0;
}

Measured memory_bytes: 256
nums = list(map(int, input().split()))
nums.sort()
A , B , C = nums[0], nums[1], nums[2]
if (B-A) % 2 == 0:
    print((C-B) + (B-A)//2)
else:
    print((C+1-B) + (B-A-1)//2 + 1)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<n+1;i++)
typedef long long ll;
typedef vector<string> vec;

int main(){
  long n,ans=0; cin>>n;
  rep(i,n){
    if(i%3!=0&&i%5!=0)ans+=i;
  }
    
  cout<<ans;

}

Measured memory_bytes: 3640
#include<iostream>
#include<queue>
using namespace std;
int main(){
  while(1){
    int w,h,s,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},an=1;
    string mp[20];
    queue<int> t;
    cin>>w>>h;
    if(w==0)break;
    for(int i=0;i<h;i++){
      cin>>mp[i];
      for(int j=0;j<w;j++)if(mp[i][j]=='@')s=w*i+j;
    }
    t.push(s);
    while(!t.empty()){
      s=t.front();
      int x=s%w,y=s/w;
      t.pop();
      for(int i=0;i<4;i++){
	int x1=x+dx[i],y1=y+dy[i];
	if(0<=x1&&x1<w&&0<=y1&&y1<h){
	  if(mp[y1][x1]=='.'){
	    t.push(w*y1+x1);
	    mp[y1][x1]='#';
	    an++;
	  }
	}
      }
    }
    cout<<an<<endl;
  }
  return 0;
}

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

struct Edge{
  int e, d, to;
  Edge(int e, int d, int to):
    e(e), d(d), to(to) {}
};

bool operator<(const Edge& a, const Edge& b){
  return a.e != b.e ? a.e < b.e : a.d != b.d ? a.d < b.d : a.to < b.to;
}

int solve(vector< vector<Edge> > &G, int L){
  int N = G.size(), INF = 1e9;
  vector< vector<int> > DP(N, vector<int>(L+1,INF));
  priority_queue<Edge> wait;
  wait.push(Edge(0,L,0));
  while(!wait.empty()){
    int e = -wait.top().e, l = wait.top().d, v = wait.top().to;
    wait.pop();
    if(e >= DP[v][l]) continue;
    DP[v][l] = e;
    for(int i = 0; i < G[v].size(); ++i){
      int e_ = G[v][i].e, d_ = G[v][i].d, v_ = G[v][i].to;
      if(e+e_ < DP[v_][l]) wait.push(Edge(-(e+e_),l,v_));
      if(l >= d_ && e < DP[v_][l-d_]) wait.push(Edge(-e,l-d_,v_));
    }
  }
  int ret = INF;
  for(int i = 0; i <= L; ++i) ret = min(ret,DP[N-1][i]);
  return ret;
}

int main(){
  int N, M, L;
  while(cin >> N >> M >> L, N){
    vector< vector<Edge> > G(N);
    int a, b, d, e;
    for(int i = 0; i < M; ++i){
      cin >> a >> b >> d >> e;
      --a;--b;
      G[a].push_back(Edge(e,d,b));
      G[b].push_back(Edge(e,d,a));
    }
    cout << solve(G,L) << endl;
  }
  return 0;
}



Measured memory_bytes: 7672
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<cmath>
#include<limits>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 100000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
using namespace std;

int main() {
    int N, M; cin >> N >> M;
    vector<int> p(M);
    vector<string> S(M);
    vi Problems(N);
    rep(i, M) {
        cin >> p[i] >> S[i];
    }
    ll Num_AC = 0;
    ll Num_WA = 0;
    for (int i = 0; i < M; i++) {
        if (Problems[p[i] - 1] != -1) {
            if (S[i] == "WA") {
                Problems[p[i] - 1]++;
            }
            else {
                Num_WA += Problems[p[i] - 1];
                Num_AC++;
                Problems[p[i] - 1] = -1;
            }
        }
    }

    cout << Num_AC << " " << Num_WA << endl;
}


Measured memory_bytes: 6528
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define i_inf int(1e9)
#define i_half_inf int(1e5)
#define ll_inf ll(1e9)*ll(1e9)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

string s;
unordered_map<char, vector<int> > mp;

void solve() {
    int ans = i_inf;
    rep(i, s.length()) mp[s[i]].emplace_back(i);
    each(m, mp) {
        int pre = -1, d_max = 0, to_last = i_inf;
        each(i, m.second) {
            int d = pre == -1 ? i : i - pre - 1;
            pre = i;
            d_max = max(d_max, d);
            to_last = min(to_last, int(s.length() - 1 - i));
        }
        ans = min(max(d_max, to_last), ans);
    }
    cout << ans << endl;
}

int main() {
    cin >> s;
    solve();
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;

#define ll long long
#define pal pair<long,long>
#define pad pair<double,double>
#define PB push_back
#define MP make_pair
#define F first
#define S second

const ll MOD = 1e9+7;
const ll INF = 1e18;
const double EPS = 1e-8;

long long pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return ret;
}

template<typename T,typename U>
bool chmax(T& max, const U& x){
	if(max<x){
		max = x;
		return true;
	}
	return false;
}

template<typename T,typename U>
bool chmin(T& min, const U& x){
	if(min>x){
		min = x;
		return true;
	}
	return false;
}


int main(){
	ll n,ans=1;
	cin >> n;
	ll a[n];
	double sub=1;
	for(ll i=0;i<n;i++){
		cin >> a[i];
		if(a[i]==0){
			cout << 0 << endl;
			return 0;
		}
	}
	for(ll i=0;i<n;i++){
		double tmp;
		tmp = (double)a[i];
		sub *= tmp;
		if(sub > 4*1e18 ){
			cout << -1 << endl;
			return 0;
		}
	}
	for(ll i=0;i<n;i++){
		ans *= a[i];
		
		if(ans>1000000000000000000){
			ans = -1;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 4376
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int h,w; cin >> h >> w;
	int cost[10][10],a[h][w];
	for(int i=0; i<10; i++){
		for(int j=0; j<10; j++){
			cin >> cost[i][j];
		}
	}
	for(int i=0; i<10; i++){
		for(int j=0; j<10; j++){
			for(int k=0; k<10; k++){
				cost[j][k] = min(cost[j][k], cost[j][i]+cost[i][k]);
			}
		}
	}
	int ans=0;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			cin >> a[i][j];
			if(a[i][j]==-1||a[i][j]==1)continue;
			else ans += cost[a[i][j]][1];
		}
	}
	cout << ans << endl;
}	


Measured memory_bytes: 384
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef pair<int ,int > P;

int n,w;
int v[102];
void solve() {
    int h = 0;
    int maxi = 0;
    int t[202] = {};

    rep(i,n) cin>>v[i];
    rep(i,n) t[v[i]/w]++;
    rep(i,202) h=max(h,t[i]);
    rep(i,202) if(t[i]) maxi=max(maxi,i);

    double ans = 0.01;
    rep(i,maxi+1) ans += 1.0*t[i]/h * 1.0*(maxi-i)/maxi;
    printf("%.10lf\n",ans);
}
int main() {
    while(cin>>n>>w) {
        if(n+w==0) return 0;
        solve();
    }
    return 0;
}

Measured memory_bytes: 1172
N = int(input())
Vs = [int(i) for i in input().split()]
Vs.sort(reverse=True)

result = []

for i, v in enumerate(Vs):
    if i == N-1:
        result.append(v*(0.5)**(i))
    else:
        result.append(v*(0.5)**(i+1))

print(sum(result))

Measured memory_bytes: 3060
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	string s;
	cin>>s;
	int l=0;
	int r=s.size()-1;
	int ans=0;
	while(l<r)
	{
		if(s[l]==s[r]){
			l++;
			r--;
		}
		else{
			if(s[l]=='x')
			{
				l++;
				ans++;
			}
			else if(s[r]=='x')	
			{
				r--;
				ans++;
			}
			else
				break;
		}
	}
	if(l<r)
		cout<<"-1"<<endl;
	else
		cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using vec_int = vector<int>;
using P = pair<int,int>;
using T = tuple<int,int,int>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;

int main(){
    int N, M; cin>>N>>M;
    //要するに二人の数の差は常に同じ
    //|ai-bi|およびN-|ai-bi|にダブりが出ないように決めればいい

    if(N%2==1){
    rep(i,M){
        cout<<1+i<<" "<< N-i<<endl;
    }
    }else{

    rep(i,M/2){
        cout<<1+i<<" "<< N-i<<endl;
        cout<<N/2-1-i<<" "<< N/2+1+i<<endl;
    }
    if(M%2==1){
        cout<<1+(int)M/2<<" "<< N-(int)M/2<<endl;
    }
    }



    return 0;
}

Measured memory_bytes: 3660
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
    int N; cin >> N;
    vector<int> L(N);
    rep(i,N) cin >> L[i];
    sort(L.begin(),L.end());
    int ans = 0;
    rep(i,N-2)repr(j,i+1,N-1){
        repr(k,j+1,N){
            if(L[k] < L[i]+L[j]) ans++;
            else break;
        }
    }
    cout << ans << endl;
}


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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  string S;
  IN(S);
  REP(i,S.size()){
    if(i%2==1) continue;
    printf("%c", S[i]);
  }
  printf("\n");

  return 0;
}

Measured memory_bytes: 592
/// max leng ver = n/2 -- > just visit i | h_k(i) < h_k-1 (i) --> n*n * (n/2) time
#include <bits/stdc++.h>

using namespace std;
#define pii pair<long long, long long>
#define F first
#define S second
const int N=501;
int h[N][N], dd[N][N], n;
map <int, pii > ma;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
void DFS(int row, int col) {
    int res = h[row][col] + dd[row][col];
    for(int i=0 ; i<4 ; ++i) {
        int xx = row + dx[i];
        int yy = col + dy[i];
        if(xx < 1 || yy < 1 || xx > n || yy > n) continue;
        if(res < h[xx][yy]) {
            h[xx][yy] = res;
            DFS(xx, yy);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(fopen(".inp", "r")) freopen(".inp", "r", stdin);
    cin >> n;
    for(int i=1 ; i<=n ; ++i)
        for(int j=1 ; j<=n ; ++j) {
            ma[(i-1)*n + j] = make_pair(i, j);
            dd[i][j] = 1;
            h[i][j] = min( {i-1, j-1, n-i, n-j});
        }
    int ans=0;
    for(int i=1 ; i<=n*n ; ++i) {
        int u; cin >> u;
        auto P = ma[u];
        int row = P.F, col = P.S;
        dd[row][col] = 0;
        ans += h[row][col];
        DFS(row, col);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 36612
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=100000+10;

int n,a[N],p[N];
ll ans[N];

int main() {
	n=read();
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=1;i<=n;++i) p[i]=i;
	sort(p+1,p+n+1,[](int x,int y) {
		return a[x]!=a[y]?a[x]>a[y]:x>y;
	});
	for (int i=1,x=1e9;i<=n;++i) {
		if (i!=n&&a[p[i+1]]==a[p[i]]) continue;
		x=min(x,p[i]);
		ans[x]+=1ll*i*(a[p[i]]-a[p[i+1]]);
	}
	for (int i=1;i<=n;++i) printf("%lld\n",ans[i]);
	return 0;
}

Measured memory_bytes: 5304
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define ill long long
#define fcout cout << fixed << setprecision(10)
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  rep(i, 0, n) cin >> v[i];
  int sum = 0;
  rep(i, 0, n) {
    if(v[i] % 2 == 1 && i % 2 == 0) sum++;
  }
  cout << sum << "\n";
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

void printvec(vi& x, int size = 0) {
    if (x.size() == 0) {
        cout << endl;
        return;
    }
    cout << x.front();
    for (int i = 1; i < (size == 0 ? x.size() : size); i++) {
        cout << " " << x[i];
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    vi as(n);
    for (int i = 0; i < n; i++) {
        cin >> as[i];
    }
    int q;
    cin >> q;
    while (q--) {
        int b, e;
        cin >> b >> e;
        reverse(as.begin() + b, as.begin() + e);
    }

    printvec(as);
}


Measured memory_bytes: 3108
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
string s;
int ans=1e9;
int main() {
	cin>>s;
	int n=s.length();
	s=" "+s;
	for(int i=1;i<n;i++)
		if(s[i]!=s[i+1])
			ans=min(ans,max(i,n-i));
	writeln(ans==1e9?n:ans);
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <vector>
#include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9+5;
const int mod = 1e9+7;
bool isPrime(int n) {
    for(int i=2;i*i<=n;i++) {
        if(n%i==0) {
            return false;
        }
    }
    return true;
}
signed main(){
    int q;
    cin >> q;
    vector<int> a(100001);
    FOR(i,3,100001) {
        if(isPrime(i) && isPrime((i+1)/2)) {
            a[i]=a[i-1]+1;
        }else {
            a[i]=a[i-1];
        }
    }

    rep(i,q) {
        int l,r;
        cin >> l >> r;
        cout << a[r]-a[l-1] << endl;
    }

    return 0;

}


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

using namespace std;

#define reps(i, n, m) for (int i = (int) (n); i < (int) (m); i++)
#define rep(i, n) reps(i, 0, n)

struct edge {
	int to;
	int flow;
	int cost;
	int rev;
	edge(int a, int b, int c, int d) : to(a), flow(b), cost(c), rev(d) {}
};

int N;
vector<vector<edge>> e;
const int INF = 1e9;

void add_edge(int from, int to, int flow, int cost)
{
	e[from].emplace_back(to, flow, cost, e[to].size());
	e[to].emplace_back(from, 0,  -cost, e[from].size()-1);
}

bool init()
{
	cin >> N;
	if (N == 0) return false;	
	e.clear();
	e.resize(N * 2 + 2);
	const int S = N * 2;
	const int G = N * 2 + 1;
	vector<tuple<int, int,int>> s;
	rep(i, N) {
		add_edge(S, i, 1, 0);
		int t = i + N;
		add_edge(t, G, 1, 0);
	}
	rep(i, N) {
		int a, b, c;
		cin >> a >> b >> c;
		vector<int> t{a, b, c};
		sort(t.begin(), t.end());
		s.emplace_back(t[0], t[1], t[2]);
	}
	sort(s.begin(), s.end());
	rep(i, N) {
		int cost = get<0>(s[i]) * get<1>(s[i]) * get<2>(s[i]);
		add_edge(i, G, 1, cost);
		reps(j, i+1, N) {
			if (get<0>(s[i]) < get<0>(s[j]) &&
				get<1>(s[i]) < get<1>(s[j]) &&
				get<2>(s[i]) < get<2>(s[j])) {
				add_edge(i, j + N, 1, 0);
			}
		}
	}
	return true;
}


int min_cost_flow(int s, int t, int f, int V)
{
	int res = 0;
	vector<int> dist(V, INF);
	vector<int> prevv(V);
	vector<int> preve(V);
	while (f > 0) {
		fill(dist.begin(), dist.end(), INF);
		dist[s] = 0;
		bool update = true;
		while (update) {
			update = false;
			rep(v, V) {
				if (dist[v] == INF) continue;
				rep(i, e[v].size()) {
					edge& E = e[v][i];
					if (E.flow > 0 && dist[v] + E.cost < dist[E.to]) {
						dist[E.to] = dist[v] + E.cost;
						prevv[E.to] = v;
						preve[E.to] = i;
						update = true;
					}
				}
			}
		}
		if (dist[t] == INF) return -1;
		int d = f;
		for (int v = t; v != s; v = prevv[v]) {
			d = min(d, e[prevv[v]][preve[v]].flow);
		}
		f -= d;
		res += d * dist[t];
		for (int v = t; v != s; v = prevv[v]) {
			edge& E = e[prevv[v]][preve[v]];
			E.flow -= d;
			e[v][E.rev].flow += d;
		}
	}
	return res;
}

int solve()
{
	return min_cost_flow(N * 2, N * 2 + 1, N, N * 2 + 2);
}

int main()
{
	while (init()) {
		cout << solve() << endl;
	}
}




Measured memory_bytes: 3284
ant = []
for i in range(5):
    ant0 = int(input())
    ant.append(ant0)
k = int(input())
if ant[1] - ant[0] > k:
    print(':(')
elif ant[2] - ant[0] > k:
    print(':(')
elif ant[3] - ant[0] > k:
    print(':(')
elif ant[4] - ant[0] > k:
    print(':(')
else:
    print('Yay!')

Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

#define chmax(a, b) (a) = max(a, b)
#define chmin(a, b) (a) = min(a, b)

int main() {
  string s;
  cin >> s;

  int K;
  cin >> K;

  string t(s);
  t[0] = '$';

  int scnt = 0;
  rep(i, s.size() - 1) {
    if (s[i + 1] == s[i]) {
      s[i + 1] = '$';
      scnt++;
    }
  }

  int tcnt = 1;
  rep(i, t.size() - 1) {
    if (t[i + 1] == t[i]) {
      t[i + 1] = '$';
      tcnt++;
    }
  }

  if (s.back() != s[0]) {
    cout << (int64_t)scnt * K << endl;
  } else if (t.back() != s[0]) {
    cout << (int64_t)K / 2 * (scnt + tcnt) + (int64_t)K % 2 * scnt << endl;
  } else {
    cout << scnt + (int64_t)(K - 1) * tcnt << endl;
  }
  return 0;
}

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

using namespace std;

#define F 		first
#define S 		second
#define ll 		long long
#define ld 		long double
#define pii		pair<ll, ll>
#define vi		vector<ll>
#define si 		set<ll>
#define mii 	map<int, int>
#define umii 	unordered_map<ll, ll>
#define pb		push_back
#define mk		make_pair
#define all(a)	a.begin(), a.end()
#define ask(x) 	cerr << #x << " = " << x << "\n";
#define INF 	1000000007
#define hell 	998244353

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	ll n, res = 0, c, x;

	cin >> n;

	if (n == 1) {
		cout << 0;
		return 0;
	}

	for (ll i = 2; i * i <= n; ++i) {
		c = 0, x = 1;
		while (n % i == 0) {
			n /= i;
			++c;
		}
		while (c >= x) {
			c -= x;
			++x;
			++res;
		}
	}
	if (n > 1)
		++res;

	cout << res;

	return 0;
}

Measured memory_bytes: 3644
package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

////////////////////////////////////////
///        templates                 ///
////////////////////////////////////////

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
        sc.Scan()
        return sc.Text()
}

var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func readBigLine() string {
        buf := make([]byte, 0, 1000000)
        for {
                l, p, e := rdr.ReadLine()
                if e != nil {
                        panic(e)
                }
                buf = append(buf, l...)
                if !p {
                        break
                }
        }
        return string(buf)
}

func strSprit(str string) []string {
        cols := strings.Split(str, " ")
        return cols
}

func parseInt(str string) int {
        n, _ := strconv.Atoi(str)
        return n
}

func intSprit(str string) []int {
        strs := strSprit(str)
        cols := make([]int, len(strs))
        for i, v := range strs {
                cols[i] = parseInt(v)
        }
        return cols
}

func bitCount(n uint) int {

        x := uint64(n)

        const m = 1<<64 - 1
        const m0 = 0x5555555555555555
        const m1 = 0x3333333333333333
        const m2 = 0x0f0f0f0f0f0f0f0f

        x = x>>1&(m0&m) + x&(m0&m)
        x = x>>2&(m1&m) + x&(m1&m)
        x = (x>>4 + x) & (m2 & m)
        x += x >> 8
        x += x >> 16
        x += x >> 32

        return int(x) & (1<<7 - 1)
}

func bitExist(n, i int) bool {
        return ((n >> uint(i)) & 1) == 1
}

////////////////////////////////////////
///        end templates             ///
////////////////////////////////////////
func chmax(dp [][]int, idx, dir, n int) {
        if dp[idx][dir] < n {
                dp[idx][dir] = n
        }
}

func main() {
        s := readBigLine()
        t := readBigLine()

        dp := make([][]int, 3010)
        for i := 0; i < 3010; i++ {
                dp[i] = make([]int, 3010)
        }

        for i := 0; i < len(s); i++ {
                for j := 0; j < len(t); j++ {
                        if s[i] == t[j] {
                                chmax(dp, i+1, j+1, dp[i][j]+1)
                        }
                        chmax(dp, i+1, j+1, dp[i+1][j])
                        chmax(dp, i+1, j+1, dp[i][j+1])
                }
        }

        res := ""
        si := len(s)
        ti := len(t)
        for si > 0 && ti > 0 {
                if dp[si][ti] == dp[si-1][ti] {
                        si--
                } else if dp[si][ti] == dp[si][ti-1] {
                        ti--
                } else {
                        res = string(s[si-1]) + res
                        si--
                        ti--
                }
        }
        fmt.Println(res)
}

Measured memory_bytes: 80640
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


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

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(1);

  int N, K;

  std::cin >> N >> K;

  if (K % 2) {
    long long c = N / K;
    
    std::cout << c * c * c << std::endl;
  }
  else {
    long long c = N / (K / 2), c1 = N / K, c2 = c - c1;
    
    std::cout << c1 * c1 * c1 + c2 * c2 * c2 << std::endl;
  }

  return 0;
}


Measured memory_bytes: 256
import os
S = input()
T = input()

T_idx = 0
def can_apply(s, t):
    for i in range(len(t)):
        if s[i] == t[i] or s[i] == '?':
            continue
        else:
            return False
    return True

start_idx = -1
for i in range(len(S)-len(T)+1):
    if can_apply(S[i:i + len(T)], T):
        start_idx = i

if start_idx < 0:
    print("UNRESTORABLE")
    os.sys.exit()
ans = [S[i] for i in range(len(S))]
for i in range(len(T)):
    if ans[start_idx + i] == '?':
        ans[start_idx + i] = T[i]

for i in range(len(ans)):
    if ans[i] == '?':
        ans[i] = 'a'

ans_str = ""
for _a in ans:
    ans_str += _a
print(ans_str)

Measured memory_bytes: 3064
s = input()
n = 0
ans = 0
mods = [0]*2019
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n = (n+int(j)*pow(10, i, 2019))%2019
  mods[n] += 1
for i in mods: ans += i*(i-1)//2
print(ans)

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

#define LL long long
#define pii pair<int,int>
using namespace std;
const int inf = 2147483647;

int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}
void put(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

char ss[200001];

int main() {
	scanf("%s", ss + 1);
	int len = strlen(ss + 1);
	int ans = 1, l = 1;
	for(int i = 2; i <= len; i++) {
		if(l == 1) {
			if(ss[i] == ss[i - 1]) {
				if(i == len) continue;
				l = 2, ans++, i++;
			} else ans++;
		} else {
			l = 1, ans++;
		}
	} put(ans);
	return 0;
}


Measured memory_bytes: 384
def myAnswer(K:int,A:int,B:int) -> int:
   if((B - A) <=2):
      return K + 1
   else:
      return max(0,(K - (A - 1)) // 2)*(B - A) + A + (K - (A - 1)) % 2


def modelAnswer():
   return
def main():
   K,A,B = map(int,input().split())
   print(myAnswer(K,A,B))
if __name__ == '__main__':
   main()

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

using namespace std;

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

  string s;
  cin >> s;
  set<char> a;
  for (auto &ch : s) {
    a.insert(ch);
  }
  bool ok = 1;
  if (a.count('S')) ok &= a.count('N');
  if (a.count('N')) ok &= a.count('S');
  if (a.count('E')) ok &= a.count('W');
  if (a.count('W')) ok &= a.count('E');
  if (ok) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

long long dp[110][100010];
int main(){
    rep(i,110)rep(j,100010) dp[i][j]=LINF;
    int n,W; cin>>n>>W;
    int w[n],v[n]; rep(i,n) cin>>w[i]>>v[i];
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<100010;j++){
            if(j-v[i-1]>=0) dp[i][j]=dp[i-1][j-v[i-1]]+w[i-1];
            dp[i][j]=min(dp[i][j],dp[i-1][j]);
        }
    }
    int ans=0;
    rep(i,100010){
        if(dp[n][i]<=W) ans=max(ans,i);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 86144
n,q=map(int,input().split())
bit=[0]*(n+1)
def add(a,w):
    x=a
    while(x<=n):
        bit[x]+=w
        x+=x&(-x)
def sum(a):
    ret=0
    x=a
    while(x>0):
        ret+=bit[x]
        x-=x&(-x)
    return ret
for j in range(q):
    com,x,y=map(int,input().split())
    if com==0:
        add(x,y)
    else:
        print(sum(y)-sum(x-1))



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

typedef long long ll;
const int N = 1e5 + 5;
int a[N];
int n;

bool check(int id) {
    ll s = a[id];
    for (int i=1; i<=n; ++i) if (i != id) {
        if (a[i] > s*2) return false;
        s += a[i];
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; ++i) {
        scanf("%d", &a[i]);
    }
    sort(a+1, a+n+1);
    int low = 1, high = n, ans = 0;
    while (low < high) {
        int mid = low + high >> 1;
        if (check(mid)) {
            ans = mid;
            high = mid;
        } else low = mid + 1;
    }
    if (ans) ans = n - ans + 1;
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define __ ios::sync_with_stdio(0), cin.tie(NULL);
#define endl "\n"
const int MAX = 100001;
using namespace std;

int n,m;
int l,r,d;
int nl[MAX];
int dis[MAX];
int vis[MAX];
int wrong;
int vs;
vector<pair<int,int> > c[MAX];

void dfs(int p){
	vis[p] = 1;
	++vs;
	for(pair<int,int> i:c[p]){
		if(!vis[i.first]){
			dis[i.first] = dis[p] + i.second;
			dfs(i.first);
		}
		else{
			if(dis[p]+i.second != dis[i.first]){
				wrong = 1;
				return;
			}
		}
	}
}

int main(){
	cin >> n >> m;

	while(m-- && cin >> l >> r >> d){
		c[l].push_back(make_pair(r,d));
		nl[r] = 1;
	}

	for(int i=1; i<=n; i++){
		if(nl[i]) continue;
		dfs(i);
	}

	if(wrong || vs<n) cout << "No\n";
	else cout << "Yes\n";

}

Measured memory_bytes: 9984
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <stack>
using namespace std;

int main()
{
  vector<string> v;
  string str, s;

  getline(cin, str);
  stringstream ss{str};

  while (getline(ss, s, ' '))
  {
    v.push_back(s);
  }

  stack<int> st;
  for (const string &s : v)
  {
    try
    {
      int n = std::stoi(s);
      st.push(n);
    }
    catch (...)
    {
      int y = st.top();
      st.pop();
      int x = st.top();
      st.pop();
      if (s == "+")
      {
        st.push(x + y);
      }
      else if (s == "-")
      {
        st.push(x - y);
      }
      else if (s == "*")
      {
        st.push(x * y);
      }
      else if (s == "/")
      {
        st.push(x / y);
      }
    }
  }

  cout << st.top() << endl;
}


Measured memory_bytes: 3344