akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll gcd(ll a,ll b){
	if(b==0)return a;return gcd(b,a%b);
}



ll lt[1234][1234], rt[1234][1234], upper[1234][1234], lower[1234][1234];

int dist(int x1, int y1, int x2, int y2){
    return abs(x1-x2)+abs(y1-y2);
}


int arr[12345678];

int main(){
    //freopen("ip.txt", "rt", stdin);
    //freopen("op.txt", "wt", stdout);

    string s;
    cin >> s;
    for(int i = 0; i < s.size()-1; i++){
        if(s[i] == 'A' && s[i+1] == 'C'){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
}


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

int main() {
	int n;
	cin >> n;
	vector<int> x(n+1), y(n+1), t(n+1);
	t[0] = 0;
	x[0] = 0;
	y[0] = 0;
	rep(i,n) cin >> t[i+1] >> x[i+1] >> y[i+1];

	bool is_exist = true;
	rep(i,n) {
		int d = abs(t[i+1] - t[i]) - abs(x[i+1] - x[i]) - abs(y[i+1] - y[i]);
		if ((d < 0) || (d % 2 == 1)) is_exist = false;  
	}
	if (is_exist) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

int main() {
    int l; cin >> l;
    double a = l/(double)3;

    double ans = (double)pow(a, 3);

    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=a;i<=n;++i)
#define lpd(i,a,n) for(int i=a;i>=n;--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 200002;
int n,a[N],b[N];

int main(){
    readi(n);
    lp(i,1,n){
        int l,r;
        read2i(l,r);
        ++a[l+N/2], ++b[r+N/2];
    }

    ++a[0+N/2], ++b[0+N/2];

    lp(i,1,N-1) b[i] += b[i-1];
    lpd(i,N-2,0) a[i] += a[i+1];

    ll ans = 0;
    lp(i,0,N-2) ans += min(b[i], a[i+1]);
    cout <<2*ans;
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/


Measured memory_bytes: 1792
N, A, B, C = map(int, input().split())
L = [0]*N
for i in range(N):
    L[i] = int(input())
INF = 10 ** 9


def dfs(times, a, b, c):  #  a,b,c:現在の竹の長さ
    if times == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
    # 適切な竹に対して、(A or B or Cに合成する) or (使わない)の場合に分ける
    no_pattern = dfs(times + 1, a, b, c)
    a_pattern = dfs(times + 1, a + L[times], b, c) + 10
    b_pattern = dfs(times + 1, a, b + L[times], c) + 10
    c_pattern = dfs(times + 1, a, b, c + L[times]) + 10

    return min(no_pattern, a_pattern, b_pattern, c_pattern)


print(dfs(0,0,0,0))

Measured memory_bytes: 43996
// D.cpp
// Date: 24:34:09 20 05 2020
// Author: bonelord
#include <bits/stdc++.h>
using namespace std;

int N, W;
long dp[100001];

void solve(){
	cin>>N>>W;
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= N; ++i){
		int w,v;
		cin>>w>>v;
		for (int j = W - w; j >= 0; --j){
			dp[w+j] = max(dp[w+j], dp[j] + v);
		}
	}
	long res = 0;
	for (int i = 0; i <= W; ++i){
		res = max(res, dp[i]);
	}
	cout<<res<<"\n";
}

main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.setf(ios::fixed);
#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("err", "w", stderr);
#endif
//	int t; cin>>t; while (t--)
	solve();
}


Measured memory_bytes: 1024
#!/usr/bin/ruby

require 'pp'

H,N  = gets.chomp.split(" ").map(&:to_i)

attacks = []
1.upto(N){|i|
  a,b  = gets.chomp.split(" ").map(&:to_i)
  attacks << [a,b]
}

table = []

1.upto(H){|h|
  min = 999999999
  attacks.each{|a|
     remaining = h - a[0]
     used = a[1]
     if remaining > 0
         used += table[remaining]
     end

     if used < min
       min = used
     end
  }

  table[h] = min
}

puts table[H]


Measured memory_bytes: 2428
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
typedef pair<int,int>P;
 
int main() {
  int a;
  cin>>a;
  string s;
  cin>>s;
  vector<int>west(a);
  int e=0,w=0;
  for(int i=0;i<a;i++){
     west.at(i)=w;
    if(s.at(i)=='W'){
      w++;
    }
  }
  for(int j=a-1;j>=0;j--){
    west.at(j)+=e;
     if(s.at(j)=='E'){
      e++;
    }
  }
  sort(west.begin(),west.end());
  cout<<west.at(0)<<endl;
}

Measured memory_bytes: 1796
#include<bits/stdc++.h>
#define randome_generate srand(std::chrono::high_resolution_clock::now().time_since_epoch().count())
using namespace std;
int n,k,a[3];
string t;
//0:r 1:p 2:s
int win[3][3]={{0,0,1},{1,0,0},{0,1,0}};
int qita[3][2]={{1,2},{0,2},{0,1}};
int mseq[100100];
int dp[100100][3];
vector<int> v;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k>>a[0]>>a[2]>>a[1]>>t;
	for(int i=1;i<=n;i++){
		if(t[i-1]=='r')
			mseq[i]=0;
		if(t[i-1]=='p')
			mseq[i]=1;
		if(t[i-1]=='s')
			mseq[i]=2;
	}
	int res=0;
	for(int i=1;i<=k;i++){
		int cc=0;
		for(int j=i;j<=n;j+=k){
			cc=j;
			for(int kk=0;kk<=2;kk++){
				if(j>k)
					dp[j][kk]=max(dp[j-k][qita[kk][0]],dp[j-k][qita[kk][1]])+win[kk][mseq[j]]*a[kk];
				else
					dp[j][kk]=win[kk][mseq[j]]*a[kk];
			}
		}
		res+=max(dp[cc][0],max(dp[cc][1],dp[cc][2]));
	}
	cout<<res<<endl;
	return 0;
}


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

int main(void)
{
   int n, p[100], i, f, j, a[100], b;
   char s[100][101], c[101];

   scanf("%d",&n);
   for(i=0;i<n;i++){
      scanf("%s%d",&s[i],&p[i]);
      a[i]=i+1;
   }

   for(i=0;i<n-1;i++)
      for(f=i+1;f<n;f++){
         j=0;
         while((j<strlen(s[i]))&&(j<strlen(s[f]))&&(s[i][j]==s[f][j]))
            j++;
         if((strlen(s[i])==j)&&(strlen(s[f])==j)){
            if(p[i]<p[f]){
               b=a[i];
               a[i]=a[f];
               a[f]=b;
               b=p[i];
               p[i]=p[f];
               p[f]=b;
               strcpy(c,s[i]);
               strcpy(s[i],s[f]);
               strcpy(s[f],c);
            }
         }
         else if(s[i][j]>s[f][j]){
            b=a[i];
            a[i]=a[f];
            a[f]=b;
            b=p[i];
            p[i]=p[f];
            p[f]=b;
            strcpy(c,s[i]);
            strcpy(s[i],s[f]);
            strcpy(s[f],c);
         }
      }

   for(i=0;i<n;i++)
      printf("%d\n",a[i]);
   return 0;
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long
#define mod 1000000007
#define IINF INT_MAX
#define INF 1LL << 30


int main() {
    string s; cin >> s;
    string t = s;
    reverse(ALL(t));

    int ans = 0;
    for(int i = 0; i < (int)s.size(); i++){
        if(s[i] != t[i]) ans++;
    }
    cout << ans / 2 << endl;

    return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <queue>
#include <cstring>
using namespace std;

const long long mod = pow(10, 9) + 7;

int main() {
	string S; cin >> S;
	for (int i = 0; i < S.size(); i++) {
		cout << 'x';
	}
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (int)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    string S;
    ll Q;
    cin >> S >> Q;

    deque<char> que;
    rep(i, len(S)) que.push_back(S[i]);

    bool state = true;
    rep(_,Q){
        ll T;
        cin >> T;
        if(T == 1) state = !state;
        else if(T == 2){
            ll F;
            char C;
            cin >> F >> C;
            if(!state) F = F == 1 ? 2 : 1;
            if(F == 1) que.push_front(C);
            else que.push_back(C);
        }
    }

    if(!state) rrep(i,len(que)) cout << que[i];
    else rep(i,len(que)) cout << que[i];

    return 0;
}

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

struct Work{
    long long A;
    long long B;
};

bool cmp(const Work &a, const Work &another) {
    return a.B < another.B;
};


int main(){
    int N;

    cin >> N;
    vector<long long> A(N), B(N);
    vector<Work> works(N);
    for(int i = 0; i < N; i++){
        cin >> A[i] >> B[i];

        Work w = {A[i], B[i]};
        works[i] = w;
    }

    sort(works.begin(), works.end(), cmp);

    long long t = 0;

    for(int i = 0; i < N; i++){
        t += works[i].A;

        if(t > works[i].B){
            cout << "No" << endl;
            return 0;
        }
        // cout << works[i].B << endl;
    }

    cout << "Yes" << endl;

    return 0;
}

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

typedef long long ll;
static const ll INF = 1ll<<60;
static const int MOD = 1e9+7;

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

    for(int i=0; i<3; i++) cout<<s[i];
    cout<<endl;
    
    return 0;
}

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

 int main() {
   int a,b,c,d,e,k;
   cin >> a >> b >> c >> d >> e >>k;
   // cout << a << b << c << d << e << k << endl;
   
    if((e - a) <= k){
      cout << "Yay!" << endl;
    }else if((e-a) > k){
      cout << ":(" << endl;

    }
      
} 


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

int main() {
  int a,b;
  cin >>a >> b;
  vector<string> s(a);
 for(int i = 0; i < a; i++)
   cin >>s.at(i) ;
 
  sort(s.begin(),s.end());
  
  string c ="";
  for (int i = 0; i<a ; i++){
    c += s.at(i);
  }

 cout << c <<endl;
}

Measured memory_bytes: 256
from collections import deque
N,M=map(int,input().split())
G=[ [] for _ in range(N) ]
for i in range(M):
  A,B=map(int,input().split())
  A-=1
  B-=1
  G[A].append(B)
  G[B].append(A)

searched=[0]*N
searched[0]=1
ans=[-1]*N
d=deque()
d.append(0)
while(len(d)!=0):
  tmp=d.popleft()
  for g in G[tmp]:
    if searched[g]==0:
      searched[g]=1
      d.append(g)
      ans[g]=tmp
print('Yes')
for i in ans[1:]:
  print(i+1)

Measured memory_bytes: 35776
// CppPractice.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//
#include <iostream>
using namespace std;

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

// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define INF 1000000000000000007
#define pb emplace_back
typedef vector<int> vi;
void solve(){
string a,b,s="";
cin>>a>>b;
int n=a.length(),m=b.length();
int dp[n+1][m+1];
memset(dp,0,sizeof dp);
for(int i=0;i<n;i++){
	for(int j=0;j<m;j++){
		if(a[i]==b[j]){
			dp[i+1][j+1]=1+dp[i][j];
		}
		else
		dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
	}
}
for(int i=n,j=m;i>0,j>0;){
	if(a[i-1]==b[j-1]){
		s+=a[i-1];
		i--;
		j--;
	}
	else if(dp[i-1][j]>dp[i][j-1])
	i--;
	else 
	j--;
}
reverse(s.begin(),s.end());
cout<<s<<"\n";

}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
   int t=1;
   //cin>>t;
     while(t--){
     	solve();
	 }
     return 0;
}

Measured memory_bytes: 38704
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(L):
    M = Mod(10**9 + 7)
    dp = [[0] * (len(L)+1) for _ in range(2)]
    dp[0][0] = 1
    dp[1][0] = 0

    for i, l in enumerate(map(int, L)):
        if l == 1:
            dp[0][i+1] = M.mul(dp[0][i], 2)
            dp[1][i+1] = M.add(dp[0][i], M.mul(dp[1][i], 3))
        else:
            dp[0][i+1] = dp[0][i]
            dp[1][i+1] = M.mul(dp[1][i], 3)
    return M.add(dp[0][len(L)], dp[1][len(L)])


def main():
    L = read_str()
    print(slv(L))


if __name__ == '__main__':
    main()


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


#define rp(i, k, n) for (int i = k; i < n; i++)
typedef long long ll;
typedef double ld;

ll mod = 1e9 + 7ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll inf = 1ll << 60;

using type = pair<int, ll>;
using event = pair<ll, type>;

int gcc(int n, int m) {
    int a = max({n, m});
    int b = min({n, m});
    if(b == 0) return a;
    int c;
    while(a % b != 0){
        c = a % b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    vector<event> task;
    rp(i, 0, n){
        ll s, t, x;
        scanf("%lld%lld%lld", &s, &t, &x);
        task.emplace_back(s-x, type(-1, x));
        task.emplace_back(t-x, type(0, x));
    }

    rp(i, 0, q){
        ll d;
        scanf("%lld", &d);
        task.emplace_back(d, type(1, d));
    }
    sort(task.begin(), task.end());

    multiset<ll> stop;
    rp(i, 0, task.size()){
        type now = task.at(i).second;
        if(now.first == -1) stop.insert(now.second);
        if(now.first == 0) stop.erase(stop.lower_bound(now.second));
        if(now.first == 1){
            if(stop.empty()) printf("%d\n", -1);
            else printf("%d\n", *(stop.begin()));
        }
    }
    return 0;


}

Measured memory_bytes: 26344
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    string S;
    cin >> S;
    if (S == "SSS") cout << 0 << endl;
    else if (S == "SSR" || S == "SRS" || S == "RSS" || S == "RSR") cout << 1 << endl;
    else if (S == "SRR" || S == "RRS") cout << 2 << endl;
    else cout << 3 << endl;
}


Measured memory_bytes: 3624
import collections

n =  int(input())
l = []
for i in range(n):
  l.append(input())

c = collections.Counter(l)
ans = [0 for _ in range(4)]

if "AC" in c.keys():
    ans[0] = c["AC"]
if "WA" in c.keys():
    ans[1] = c["WA"]
if "TLE" in c.keys():
    ans[2] = c["TLE"]
if "RE" in c.keys():
    ans[3] = c["RE"]

  
    
    
print("AC x " + str(ans[0]))
print("WA x " + str(ans[1]))
print("TLE x " + str(ans[2]))
print("RE x " + str(ans[3]))

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

int main() {
    string S,CS,CS2,CS3;
    int N,ans=0;
    char num1,num2,num3;
    cin >> N;
    cin >> S;
    for(int i=0;i<10;i++){
        CS  = S;
        num1 = '0' + i;
        if(CS.find(num1)==string::npos){
                    continue;
                }
        else
        {
            CS.erase(0,CS.find(num1)+1);
        }
        
        for(int j=0;j<10;j++){
            CS2=CS;
            num2 = '0' + j;
            if(CS2.find(num2)==string::npos){
                    continue;
                }
            else
            {
                CS2.erase(0,CS2.find(num2)+1);
            }
            
            for(int k=0;k<10;k++){
                CS3=CS2;
                num3 = '0' + k;
                if(CS3.find(num3)==string::npos){
                    continue;
                }
                else
                {
                    ans++;
                }
            }
        }
    }

    cout << ans <<endl;

}

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

int main(){
	string str;
	int target;
	while(cin >> target >> str, str != "0" || target != 0){
		int len = str.size() - 1;
		int ans = -1;
		int ansi = 0;
		bool reject = false;
		for(int i = 0; i < (1 << len); i++){
			int prev = 0;
			int sum = 0;
			for(int j = 0; j < len; j++){
				if(i & (1 << j)){
					sum += stoi(str.substr(prev, (j - prev)+ 1), nullptr, 10);
					prev = j + 1;
				}
			}
			sum += stoi(str.substr(prev, str.size() - prev),nullptr, 10);
			//cout << sum << endl;
			if(sum <= target){
				if(ans == sum){
					reject = true;	
				}else if(ans < sum){
					ans = sum;
					reject = false;
					ansi = i;
				}
			}
		}
		if(ans == -1){
			cout << "error" << endl;
		}else if(reject){
			cout << "rejected" << endl;
		}else{
			cout << ans;
			int prev = 0;
			for(int j = 0; j < len; j++){
				if(ansi & (1 << j)){
					cout << " " << stoi(str.substr(prev, (j - prev)+ 1),nullptr, 10);
					prev = j + 1;
				}
			}
			cout << " " << stoi(str.substr(prev, str.size() - prev),nullptr, 10);
			cout << endl;

		}

	}
}

Measured memory_bytes: 3124
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>
#include <cassert>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 62;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

void cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
//-----------------------ここから-----------
ll n;
vector<ll> a;
ll memo[200100][5][5];
ll rec(ll i, ll j, ll k){
    if(i <= 0 && j == 0 && k == 0) return 0;
    if(i <= 0) return -INF;
    if(memo[i][j][k] != -INF) return memo[i][j][k];

    ll res = -INF;
    if(k > 0) res = max(res, rec(i - 4, j, k - 1) + a[i - 4]);
    if(j > 0) res = max(res, rec(i - 3, j - 1, k) + a[i - 3]);
    res = max(res, rec(i - 2, j, k) + a[i - 2]);

    return memo[i][j][k]  = res; 
}
int main(void){
    cin >> n;
    a.resize(n);
    rep(i, n) cin >> a[i];

    vector<ll> e, o;
    e.push_back(0);
    o.push_back(0);
 
    for(int i = 0; i < n; i += 2){
        e.push_back(e.back() + a[i]);
    }
    for(int i = 1; i < n; i += 2){
        o.push_back(o.back() + a[i]);
    }

    
    if(n % 2 == 0){
        ll ans = -INF;
        ans = max(e.back(), o.back());
        for(int i = 0; i <= n / 2; i++){
            ans = max(ans, o[n / 2] - o[i] + e[i]);
        }
        cout << ans << endl;
    } else {
        rep(i, 200100){
            rep(j, 5){
                rep(k, 5){
                    memo[i][j][k] = -INF;
                }
            }
        }

        cout << max(rec(n + 1, 2, 0), rec(n + 1, 0, 1)) << endl;
    }
}


Measured memory_bytes: 51736
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <numeric>

using namespace std;
typedef long long int ll;
typedef long double ld;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }                   // 最大公約数
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };                      // 最小公倍数
ll getDigit(ll num) { return log10(num) + 1; }                         // 桁数
ll digitSum(ll n) { return (n < 10) ? n : digitSum(n / 10) + n % 10; } // 各桁の和
#define MOD 1e9 + 7
#define pb push_back
#define rep(i, n) for (ll i = 0; i < n; i++)
#define repn(i, n) for (ll i = 1; i <= n; i++)
#define repi(i, a, b) for (ll i = ll(a); i < ll(b); ++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265359

void Main()
{
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    rep(i, n - 2)
    {
        if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C')
            ++ans;
    }

    cout << ans << endl;
    return;
}

signed main(void)
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>; // グラフ型
typedef long long ll;
#define _GLIBCXX_DEBUG

int main() {
  ll N;
  cin >> N;
  vector<ll> A(N);

  for(ll i=0; i< N; i++){
    cin >>A[i];
  }

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

  for(ll i=0; i< N-1; i++){
    if(A[i] == A[i+1]){
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
  return 0;
}


Measured memory_bytes: 4840
int array[10000];
int vector[100];
int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n * m; i++){
        scanf("%d", array + i);
    }

    for (int i = 0; i < m; i++) {
        scanf("%d", vector + i);
    }

    for (int i = 0; i < n; i++) {
        int x = 0;
        for (int j = 0; j < m; j++) {
            x += array[i * m + j] * vector[j];
        }
        printf("%d\n", x);
    }
}


Measured memory_bytes: 2104
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,ma,mb = li()
drugs = [tuple(li()) for _ in range(n)]

INF = 10**18

dp = [[[INF]*401 for _ in range(401)] for _ in range(41)]
dp[0][0][0] = 0

for i in range(n):
    ai, bi, ci = drugs[i]
    for a in range(401):
        for b in range(401):
            if a+ai <= 400 and b+bi <= 400:
                dp[i+1][a+ai][b+bi] = min(dp[i][a][b] + ci,
                                          dp[i+1][a+ai][b+bi])

            dp[i+1][a][b] = min(dp[i][a][b],
                                dp[i+1][a][b])
            
ans = INF
for ai in range(1,401):
    for bi in range(1,401):
        if ai/bi == ma/mb and dp[n][ai][bi] < INF:
            ans = min(ans, dp[n][ai][bi])
            
print(ans if ans < INF else -1)

Measured memory_bytes: 101084
#include<iostream>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	if(a==b &b!=c)
	{
		cout<<"Yes";
	}
	else if(a==c && a!=b)
	{
		cout<<"Yes";
	}
	else if(b==c && a!=b)
	{
		cout<<"Yes";
	}
	else
	{
		cout<<"No";
	}
	return 0;
}

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

sum_prob = 0
for i in range(1,N+1):
  curr_score = i
  coin_heads = 0
  while curr_score < K:
    curr_score = curr_score * 2
    coin_heads += 1
  sum_prob += 1./N * (0.5)**coin_heads

print(sum_prob)

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

int main() {
    int A, B;
    cin >> A >> B;
    if (A%2 == B%2) {
        cout << (A+B)/2 << endl;
    }
    else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
from operator import itemgetter
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
AB.sort(reverse=True, key=itemgetter(1))

ans = 1
left, right = AB.pop()
while AB:
    a, b = AB.pop()
    if a >= right:
        ans += 1
        left, right = a, b
    else:
        right = min(right, b)
        left = max(left, a)
print(ans)

Measured memory_bytes: 29076
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vs = vector<string>;
using vb = vector<bool>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int n;
    cin >> n;
    cout << (n == 1 ? 0 : 1) << endl;
}


Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef vector<string> svec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-8;


void solve() {
	int h, w; cin >> h >> w;
	vector<int> dp(1 << w,-mod);
	vector<int> cop(1 << w);
	int sup = (1 << w);
	dp[0] = 0;
	vector<string> s(h);
	rep(i, h)cin >> s[i];
	rep(i, h) {
		int len = s[i].length();
		rep(j, w) {
			fill(cop.begin(), cop.end(), -mod);
			rep(k, sup) {
				if (dp[k] < 0)continue;
				//take
				int tmp = 0;
				vector<bool> b;
				rep(l, w) {
					if (k&(1 << l))b.push_back(true);
					else b.push_back(false);
				}
				rep(l, j)if (b[l])tmp++;
				int tmpall = 0;
				rep(l, w)if (b[l])tmpall++;
				if (tmp < len) {
					int nid = k * 2+1; nid %= sup;
					int val = dp[k];
					if (b[0] && j > 0) {
						if (s[i][tmp - 1] == s[i][tmp])val++;
					}
					if (b[w - 1]) {
						if (s[i - 1][(int)s[i - 1].length() - (tmpall - tmp)] == s[i][tmp])val++;
					}
					cop[nid] = max(cop[nid], val);
				}
				//non_take
				int nid = k * 2; nid %= sup;
				cop[nid] = max(cop[nid], dp[k]);
			}
			rep(k, sup) {
				bool f = true;
				int tmp = 0;
				rep(l, j + 1) {
					if (k&(1 << l))tmp++;
				}
				if (tmp + w - (j + 1) < len)f=false;
				if (f) {
					dp[k] = cop[k];
				}
				else {
					dp[k] = -mod;
				}

			}
		}
	}
	int ans = 0;
	rep(i, (1 << w))ans = max(ans, dp[i]);
	cout << ans*2 << endl;
}

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

	//cout << fixed << setprecision(10);
	//init();
	/*while (cin >> m >> num[0] >> num[1], m | num[0] | num[1]) {
		solve();
	}*/
	solve();
	//stop
	return 0;
}



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

typedef long long int LLI;

LLI a, b, c, d;

LLI gcd(LLI x, LLI y) {
  if (y == 0) return x;
  return gcd(y, x%y);
}

LLI calc(LLI x, LLI y) {
  return x+y - 1;
}

int main() {
  scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
  if (a == c || b == d) {
    puts("0");
    return 0;
  }

  LLI x = abs(a-c);
  LLI y = abs(b-d);
  LLI t = gcd(x, y);
  x/=t; y /= t;
  printf("%lld\n", calc(x, y) * t);
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner kbs = new Scanner(System.in);
		int a = kbs.nextInt();
		int b = kbs.nextInt();
		int c = kbs.nextInt();
		
		if(a != b && a != c && b != c) {
			System.out.println("No");
		}
		
		if(a == b && a != c && b != c) {
			System.out.println("Yes");
		}
		
		if(a != b && a == c && b != c) {
			System.out.println("Yes");
		}
		
		if(a != b && a != c && b == c) {
			System.out.println("Yes");
		}
		
		if(a == b && a == c && b == c) {
			System.out.println("No");
		}
		
		kbs.close();
	}

}


Measured memory_bytes: 21588
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define cool ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
int main()
{ 
    cool;
    int s,w;
    cin>>s>>w;
    if(w>=s)
    	cout<<"unsafe";
    else
    	cout<<"safe";
    return 0;
}


Measured memory_bytes: 3636
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace atcoder
{
	class Program
	{
		static int In => int.Parse(Console.ReadLine());
		static int[] Ins => Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
		static void Out(bool b) => Console.WriteLine(b ? "YES" : "NO");

		static void Main(string[] args)
		{
			var a = Ins;
			int h = a[0];
			int w = a[1];
			var li = new List<String>();
			int[][] n = new int[][] { new int[]{ -1, -1 },
				new int[] { -1, 0 }, new int[] { -1, 1 }, new int[] { 0, -1 },
				new int[] { 0, 1 }, new int[] { 1, -1 }, new int[] { 1, 0 }, new int[] { 1, 1 } };
			for(int i = 0;i < h;i++)
			{
				String s = Console.ReadLine();
				li.Add(s);
			}
			for(int i = 0;i < h;i++)
			{
				for(int j = 0;j < w;j++)
				{
					if (li[i][j] == '#') Console.Write("#");
					else
					{
						int count = 0;
						for(int k = 0;k < n.Length;k++)
						{
							int x = j + n[k][0];
							int y = i + n[k][1];
							if (!(0 <= x && x < w && 0 <= y && y < h)) continue;
							if (li[y][x] == '#') count++;
						}
						Console.Write(count);
					}
				}
				Console.WriteLine();
			}
			//Console.ReadLine();
		}
	}
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
	int n,A,ans=0;
	bool flag=true;
	vector<int> a;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>A;
		a.push_back(A);
	}
	while(flag){
		flag=false;
		for(int i=n-1;i>0;i--){
			if(a[i]<a[i-1]){
				int tmp=a[i-1];
				a[i-1]=a[i];
				a[i]=tmp;
				flag=true;
				ans++;
			}
		}
	}
	for(int i=0;i<n;i++){
		if(i==n-1) cout<<a[i]<<endl<<ans<<endl;
		else cout<<a[i]<<" ";
	}
	return 0;
}



Measured memory_bytes: 3136
#include<iostream>
using namespace std;
int main(){
  int n,sum=0,m=0;
  cin >> n;
  int p[n];
  for(int i=0;i<n;i++){
    cin >> p[i];
    sum+=p[i];
    m=(m>p[i])?m:p[i];
  }
  cout << sum- (m/2)<<endl;
}


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

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using usize = std::size_t;
template<typename T>
using Vector = std::vector<T>;
using String = std::string;
template<typename T>
using UniquePointer = std::unique_ptr<T>;
using namespace std;

#define rep(i, max) for(usize i = 0; i < max; ++i)
#define loop while(true)

UniquePointer<String> readLine() {
    UniquePointer<String> line(new String());
    getline(cin, *line);
    return line;
}

template<typename T1, typename T2>
pair<T1, T2> readPair(){
    T1 res1;
    cin >> res1;
    T2 res2;
    cin >> res2;
    readLine();
    return make_pair(res1, res2);
}

template<typename T>
UniquePointer<Vector<T>> readVector(usize num) {
    UniquePointer<Vector<T>> list(new Vector<T>(num));
    rep(i, num) {
        cin >> (*list)[i];
    }
    readLine();
    return list;
}

void readValues()
{
    readLine();
}

template<typename H, typename... T>
void readValues(H& head, T&&... tails){
    H a;
    cin >> a;
    head = a;
    readValues(forward<T>(tails)...);
}

template<typename T>
void writeLine(T arg) {
    cout << arg << endl;
}

template<typename T>
void write(T arg) {
    cout << arg << std::flush;
}

void program();

int main()
{
    ios::sync_with_stdio(false);
    program();
}

void program() {
    int n, k;
    readValues(n, k);
    if(k > n){
        readLine();
        writeLine(0);
        return;
    }
    auto h = readVector<i32>(n);
    sort(h->begin(), h->end());
    writeLine(accumulate(h->begin(), h->end() - k, 0LL));
}

Measured memory_bytes: 5352
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>

// template {{{
using namespace std;

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define all(x) (x).begin(), (x).end()
#define fill(x, y) memset(x, y, sizeof(x))

using int64 = long long;

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

bool in_field(int W, int H, int x, int y) {
  return (0 <= x && x < W) && (0 <= y && y < H);
}

// pair
template <typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) {
  return s << "(" << p.first << ", " << p.second << ")";
}
// vector
template <typename T> ostream &operator<<(ostream &s, const vector<T> &v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << "\t";
  }
  return s;
}

// }}}

// url: https://abc076.contest.atcoder.jp/tasks/abc076_c

string S, T;

int main() {
  cin >> S >> T;

  for (int i = S.length() - T.length(); i >= 0; i--) {
    bool match = true;
    rep(j, T.length()) {
      if ((S[i + j] != T[j] && S[i + j] != '?')) {
        match = false;
        break;
      }
    }
    if (match) {
      rep(j, T.length()) { S[i + j] = T[j]; }
      rep(j, S.length()) {
        if (S[j] == '?')
          S[j] = 'a';
      }
      cout << S << endl;
      return 0;
    }
  }

  cout << "UNRESTORABLE" << endl;
  return 0;
}

// vim: foldmethod=marker


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <set>

using namespace std;

typedef long long ll;
#define mems(p) memset(p,0,sizeof(p));
#define mp make_pair;

void fast()
{ios_base::sync_with_stdio(false);cin.tie(0);}

int main() {
	fast();
	int n,k;
	string s;
	cin>>n>>k>>s;
	s[k-1]+=32;
	cout<<s<<endl;
}

Measured memory_bytes: 256
// Winners don't quit and Quitters don't win
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mod 998244353
#define MAX 100005
vll adj[MAX];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll x,i,j,a,b;
    cin>>x;
    for(i=0;;++i){
    	for(j=-100;j<=i;++j){
    		if((pow(i,5)-pow(j,5))==x){
    			a=i;
    			b=j;
    			cout<<a<<" "<<b;
    			return 0;
			}
			if((pow(i,5)-pow(j,5))<x){
				break;
			}
		}
	}
}

Measured memory_bytes: 6436
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {

  long long int n, m;
  cin >> n >> m;

  vector< vector< long long int > > d, c;

  for ( long long int i = 0; i < m; i++ ) {
    vector< long long int > v;
    for ( long long int j = 0; j < m; j++ ) {
      long long int in;
      cin >> in;
      v.push_back( in );
    }
    d.push_back( v );
  }

  for ( long long int i = 0; i < n; i++ ) {
    vector< long long int > v;
    for ( long long int j = 0; j < n; j++ ) {
      long long int in;
      cin >> in;
      v.push_back( in );
    }
    c.push_back( v );
  }

  long long int ans = 1145141919LL;

  long long int p[3][31] = {};

  for ( long long int cc = 1; cc <= m; cc++ ) {

    for ( long long int x = 0; x < n; x++ ) {
      for ( long long int y = 0; y < n; y++ ) {

	p[(x+1+y+1)%3][cc] += d[ c[y][x]-1 ][ cc-1 ];

      }
    }

  }

  long long int co[3];

  for ( co[0] = 1; co[0] <= m; co[0]++ ) {

    for ( co[1] = 1; co[1] <= m; co[1]++ ) {
      if ( co[1] == co[0] ) continue;

      for ( co[2] = 1; co[2] <= m; co[2]++ ) {
	if ( co[2] == co[0] ) continue;
	if ( co[2] == co[1] ) continue;

	ans = min( ans, p[0][co[0]] + p[1][co[1]] + p[2][co[2]] );

      }
    }
  }


  cout << ans << endl;

}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	#ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
	int t,n;
	cin>>t>>n;
	int ar[t];
	for(int i=0;i<t;++i) cin>>ar[i];
	sort(ar,ar+t);
	int sum=0;
	for(int i=0;i<n;++i) sum+=ar[i];
	cout<<sum;
	return 0;
}

Measured memory_bytes: 3616
import sys
input = sys.stdin.readline

def main():
    n, x, m = map(int, input().split())
    cycle = [False]*m
    next_list = [-1]*m
    cycle[x] = True
    
    now = x
    count = 1
    for i in range(m):
        nex = pow(now, 2, m)
        if count == n:
            break
        if cycle[nex]:
            next_list[now] = nex
            break
        next_list[now] = nex
        cycle[nex] = True
        now = nex
        count += 1
    
    ans = 0
    if count == n:
        for i in range(m):
            if cycle[i]:
                ans += i
        
    else:
        judge = x
        while judge != now:
            ans += judge
            judge = next_list[judge]
            n -= 1
        
        key = judge
        judge = next_list[judge]

        count = 1
        while judge != now:
            key += judge
            judge = next_list[judge]
            count += 1
        
        ans += n//count * key
        n %= count
        while n > 0:
            n -= 1
            ans += judge
            judge = next_list[judge]
    

        

    print(ans)

    
    
    
    
if __name__ == "__main__":
    main()


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

int main() {
    ll n, m;
    cin >> n >> m;
    vector<P> A(n);
    rep(i,n) {
        ll a, b;
        cin >> a >> b;
        A[i] = make_pair(a,b);
    }
    sort(A.begin(),A.end());
    ll sum = 0;
    ll ans = 0;
    rep(i,n) {
        sum += A[i].second;
        if (sum <= m) ans += A[i].first*A[i].second;
        else {
            sum -= A[i].second;
            ans += A[i].first*(m-sum);
            break;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
# include <bits/stdc++.h>
using namespace std;
# define ll  long long
# define pb push_back

ll dp[100001][3]={0};
ll a[100001][3];

ll happy(ll i,ll j)
{
    if(dp[i][j]!=0) return dp[i][j];
    if(j==0)  return dp[i][j]=max(happy(i-1,1)+a[i][j],happy(i-1,2)+a[i][j]);
    if(j==1)  return dp[i][j]=max(happy(i-1,0)+a[i][j],happy(i-1,2)+a[i][j]);
    if(j==2)  return dp[i][j]=max(happy(i-1,1)+a[i][j],happy(i-1,0)+a[i][j]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    for(ll i=0;i<n;i++)
    {
        for(ll j=0;j<=2;j++)
        {
            cin>>a[i][j];
        }
    }
    for(ll j=0;j<=2;j++)
    {
        dp[0][j]=a[0][j];
    }
    cout<<max(happy(n-1,2),max(happy(n-1,1),happy(n-1,0)))<<endl;
}


Measured memory_bytes: 9600
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    char[] S = s.toCharArray();
    int tmp;
    boolean flag = (S[0] == 'B');
    tmp = 100;
    if(flag){
      tmp = 0;
    }
    long count = 0;
    for(int i = 1; i< S.length; i++){
      if(flag){
        if(S[i] == 'W'){
          S[tmp] = 'W';
          S[i] = 'B';
          count += i - tmp;
          tmp = tmp + 1;
        }
      }else{
        if(S[i] == 'B'){
          tmp = i;
        }
      }
      flag = (S[i] == 'B');
    }
    System.out.println(count);
  }
}

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

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

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    ll n,x,d,ans = 0;
    cin >> n >> x >> d;
    map<ll,vector<pair<ll,ll>>> mp;
    if (d == 0) {
        if (x) cout << n+1 << endl;
        else cout << 1 << endl;
        return 0;
    }
    if (d < 0) {
        d *= -1;
        x -= d*(n-1);
    }
    for (ll i = 0;i <= n;++i) {
        ll l = i*x/d+i*(i-1)/2,r = i*x/d+i*(2*n-i-1)/2;
        mp[abs(i*x)%d].push_back(make_pair(l,r));
    }
    for (auto& it : mp) {
        vector<pair<ll,ll>>& a = it.second;
        sort(a.begin(),a.end());
        ll l = -1e18;
        for (pair<ll,ll>& p : a) {
            ans += max(0LL,p.second-max(p.first,l)+1);
            l = max(l,p.second+1);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 22144
from itertools import permutations

INF = 1e+9
N, M, R = map(int, input().split())
rlist = list(map(int, input().split()))

G = [[INF]*N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = G[b-1][a-1] = c

def warshall_floyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

G = warshall_floyd(G)
sum_list = []
for tmp in permutations(rlist):
    t_sum = 0
    for i in range(len(tmp)-1):
        t_sum += G[tmp[i]-1][tmp[i+1]-1]
    sum_list.append(t_sum)

print(min(sum_list))

Measured memory_bytes: 61144
N = int(input())

X = list(map(int, input().split()))

MOD = 10**9 + 7

cnt = 1
j = 1

n_to_remove = 0

runner = 1

for i,x in enumerate(X):
  j = i+1 - n_to_remove
  if runner > x:
    n_to_remove += 1
    runner = x-1
  runner += 2
  cnt = (cnt*j)%MOD

print(cnt)

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

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;

ll monster(ll h){
  
  if(h == 1)
    return 1;
  else{
    return 1 + 2*monster(h/2);
  }
}

int main(){
  ll h;
  cin >> h;
  
  
  cout << monster(h) << endl;
  
}

Measured memory_bytes: 256
s = input()
temp = s
while len(temp) > 4:
    if temp[len(temp) - 3:] == 'eam' and temp[len(temp) - 5:] == 'dream': temp = temp[: len(temp) - 5]
    elif temp[len(temp) - 3:] == 'mer' and temp[len(temp) - 7:] == 'dreamer': temp = temp[: len(temp) - 7]
    elif temp[len(temp) - 3:] == 'ase' and temp[len(temp) - 5:] == 'erase': temp = temp[: len(temp) - 5]
    elif temp[len(temp) - 3:] == 'ser' and temp[len(temp) - 6:] == 'eraser': temp = temp[: len(temp) - 6]
    else: break
if len(temp) > 4: print('NO')
else: print('YES')

Measured memory_bytes: 3316
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int x = Integer.parseInt(sa[0]);
		int y = Integer.parseInt(sa[1]);
		br.close();

		int a = y - x;
		if (a < 0) {
			a = Integer.MAX_VALUE;
		}
		int b = Math.abs(Math.abs(x) - Math.abs(y));
		if (x < 0) {
			if (y <= 0) {
				b += 2;
			} else {
				b++;
			}
		} else {
			if (y <= 0) {
				b++;
			} else {
				b += 2;
			}
		}
		System.out.println(Math.min(a, b));
	}
}


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

int main(){
 long long int a,b,x,i,j;
  while(cin>>x) {
  for(i=0;i<=200;i++){
      a = i*i*i*i*i;
      int f=0;
     for(j=0;j<=200;j++){
      b=j*j*j*j*j;
      //cout<<"a: "<<i<<'-'<<a<<" b: "<<j<<'-'<<b<<endl;
       if(a-b == x){
        cout<<i<<' '<<j<<endl;
        f=1;
        break;
       }
       if(a+b == x) {
        cout<<i<<' '<<-1*j<<endl;
        f=1;
        break;
       }
       if(-1*a + b == x){
        cout<<-1*i<<' '<<-1*j<<endl;
        f=1;
        break;
       }
    }
    if(f==1) break;
   }
  }
   return 0;
}


Measured memory_bytes: 3596
#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)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, a;  cin >> n >> a;
    cout << n * n - a << '\n';

    return 0;
}


Measured memory_bytes: 256