akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef unsigned long long int ull;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w)
{
	cout<<w.size()<<endl;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<endl;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=10;
		k+=a[i]-'0';
	}
	return k;
}

string its(ll k)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%10)+'0');
		k/=10;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

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;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

const int N=3010;
int n,m,h[N][N],mm;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829)+13893829);
	cin>>n>>m;
	for (int i=0;i<n;++i)
	{
		for (int j=0;j<m;++j) cin>>h[i][j];
		for (int k=0;k<i;++k)
		{
			int d=0;
			for (int j=0;j<m;++j) d+=(h[i][j]-h[k][j])*(h[i][j]-h[k][j]);
			if (round(sqrt(d))*round(sqrt(d))==d) ++mm;
		}
	}
	cout<<mm;
}




Measured memory_bytes: 512
S = list(input())
Q = int(input())
QL = []

for _ in range(Q):
    QL.append(input())

inversed = False
invc = 0

prefix = []
suffix = []

for query in reversed(QL):
    # print("qi:", query)
    if query == '1':
        #1
        inversed = not inversed
        invc += 1
    
    else:
        # print("2:inv:", inversed)
        #2
        __, f, c = query.split()

        if f == '1':
            if inversed:
                suffix.append(c)
            else:
                prefix.append(c)
        else:
            if not inversed:
                suffix.append(c)
            else:
                prefix.append(c)

# print("prefix:", prefix)
# print("suffix:", suffix)

if inversed:
    S = list(reversed(S))

print("".join(prefix) + "".join(S) + "".join(list(reversed(suffix))))

Measured memory_bytes: 26112
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using ll = long long;
using namespace std;


void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int x,a,b,w,q;
    cin >> x>>a>>b;
    w=abs(x-a);
    q=abs(x-b);
    if (w<q) cout<<"A";
    else cout << "B";
    


    return 0;
}

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

int main(){
    int a,b;
    cin >> a >> b;
    int east_h = 0;
    for (int i = 1;i <= b-a-1;i++){
        east_h += i;
    }

    cout << east_h - a << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

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

int main() {
    int k, a, b; cin >> k >> a >> b;
    if (a % k == 0 || k * (a / k) + k <= b) cout << "OK" << endl;
    else cout << "NG" << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vp;
typedef pair<int,int> pii;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9+7;
const int MAX = 10000000;
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
//cout << 'H' << endl;
//next_permutation(ALL(p));
//typedef priority_que<int> pque;//これは大きい順
//typedef priority_que<int, vector<int>, greater<int>> pque;//これは小さい順


int main(){
	string s;
	cin >> s;
	int q;
	cin >> q;
	bool reversed = false;

	rep(i,q){
		int t;
		cin >> t;
		if(t == 1){
			if(reversed == false) reversed = true;
			else reversed = false;
		}else{
			int f;
			string c;
			cin >> f >> c;
			if((reversed == false && f == 1) || (reversed == true && f == 2)){
				s.insert(0,c);
			}else{
				s += c;
			}
		}
	}
	if(reversed == true) reverse(ALL(s));
	cout << s << endl;

  return 0;
}


Measured memory_bytes: 900
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define maxn 200010
int a[maxn];
int n;
int main()
{
	scanf("%d",&n);
	int flag=0;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),flag|=a[i];
	if(!flag){
		puts("Yes"); return 0;
	}
	if(n%3){
		puts("No"); return 0;
	}
	std::sort(a+1,a+n+1);
	for(int i=1;i<n/3;i++)
		if(a[i]!=a[i+1]||a[i+(n/3)]!=a[i+(n/3)+1]||a[i+(n/3)*2]!=a[i+(n/3)*2+1]){
			puts("No"); return 0;
		}
	if(a[n/3]^a[(n/3)*2]^a[n])puts("No");
	else puts("Yes");
	return 0;
}

Measured memory_bytes: 512
S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)

Measured memory_bytes: 9184
n = int(input())
a = list(map(int,input().split()))
al = [[i,0] for i in range(n)]

for i in range(n):
    al[i][1]=a[i]

al.sort(key=lambda al:al[1])

s = ""

for i in range(n):
    s += str(al[i][0]+1)+" "

print(s[:len(s)-1])


Measured memory_bytes: 22756
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++) //for文マクロ
#define all(obj) obj.begin(), obj.end()
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef unsigned long long ull;
typedef int long long ll;
constexpr ll bigNum = 1000000007;

signed main()
{
    fast;
    //ここから本体
    ll n;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; i++)
    {
        string x;
        cin >> x;
        sort(all(x));
        a[i] = x;
    }
    sort(all(a));

    ll ans = 0;
    ll c = 1;
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + 1])
            c++;
        else
        {
            ans += (c * (c - 1)) / 2;
            c = 1;
        }
    }
    ans += (c * (c - 1)) / 2;
    cout << ans << endl;
}

Measured memory_bytes: 5760
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(M)]


low_set = set()
appear_set = set()

for i in range(M):
    a, b = AB[i]
    if H[a-1] > H[b-1]:
        low_set.add(b)
    elif H[a-1] < H[b-1]:
        low_set.add(a)
    else:
        low_set.add(a)
        low_set.add(b)

ans_set = set(range(1, N+1)) - low_set
print(len(ans_set))


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

using namespace std;
 
typedef long long ll;
 

int main(){
    string hizuke;

    cin >> hizuke;

    int heiseiflag = 0;
    if (stoi(hizuke.substr(0, 4)) <= 2019){
        if (stoi(hizuke.substr(5, 7)) <= 4){
            if (stoi(hizuke.substr(8, 10)) <= 30){
                heiseiflag++;
            }
        }
    }
    if (heiseiflag){
        cout << "Heisei" << endl;
    } else {
        cout << "TBD" << endl;
    }

}

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

int main()
{
	vector<double> vals(1001);
	for (double i = 1; i < 1001; i++) {
		vals[i] = (i * (i + 1) / 2) / i;
	}

	int n, k;
	cin >> n >> k;

	vector<int> p(n);
	vector<ll> acum(n + 1);
	acum[0] = 0;
	int a;
	rep(i, n) {
		cin >> p[i];
		acum[i + 1] = acum[i] + p[i];
	}

	int start = 0, end = 0;
	ll max_val = 0, t = 0;
	for (int i = k; i <= n; i++) {
		t = acum[i] - acum[i - k];
		if (max_val < t) {
			max_val = t;
			start = i - k;
			end = i; 
		}
	}

	double ans = 0;
	for (int i = start; i < end; i++)
		ans += vals[p[i]];

	cout << to_string(ans) << endl;
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {

	static Scanner scan = new Scanner(System.in);
	public static void main(String[] args){
		call(scan.nextInt());
	}

	/**
	 * 3の倍数と下一桁が３のときだけ出力する(世界のナベアツ式）
	 * @param n　入力する数
	 */
	public static void call(int n){

		for(int i = 1;i<=n;i++){
			//int i = 1;

			int x = i;

			if(x % 3 == 0){
				System.out.print(" "+i);
			}else{
				while(x >= 3){
					if(x % 10 == 3){
						System.out.print(" "+i);
						break;
					}
					x = x / 10;
				}
			}

		}
		System.out.println();
	}
}



Measured memory_bytes: 28768
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define cin(a) scanf("%d",&a)
#define pii pair<int,int>
#define ll long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m,k,t;

int main()
{
    cin>>n>>m>>k;
    if(n < m) swap(n,m);
    int ans = k/n;
    if(k%n) ans++;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import Data.List

main = do
  n <- readLn
  putStrLn $ show n ++ ": " ++ unwords (fmap show $ solve n)

factors :: Int -> [Int]
factors n = [d | d <- [1..n], n `mod` d == 0]

{-
isPrime :: Int -> Bool
isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x
-}
isPrime :: Int->Bool
isPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0]

primeFactor :: Int -> [Int]
primeFactor 1 = []
primeFactor n = d : primeFactor (n `div` d)
  where d = factors n !! 1

solve :: Int -> [Int]
solve n
  | isPrime n = [n]
  | otherwise = primeFactor n

primeFactor2 :: [Int] -> Int -> [Int]
primeFactor2 res 1 = res
primeFactor2 res n = primeFactor2 (d : res) (n `div` d)
    where d = factors n !! 1

Measured memory_bytes: 4204
N,M = (int(T) for T in input().split())
Stud = [[] for TN in range(0,N)]
Check = [[] for TM in range(0,M)]
for TN in range(0,N):
    Stud[TN] = [int(T) for T in input().split()]
for TM in range(0,M):
    Check[TM] = [int(T) for T in input().split()]

GoPoint = [0]*N
for TN in range(0,N):
    MIND = 10**9
    for TM in range(0,M):
        Dist = abs(Stud[TN][0]-Check[TM][0])+abs(Stud[TN][1]-Check[TM][1])
        if Dist<MIND:
            MIND = Dist
            MINI = TM
    GoPoint[TN] = MINI+1
print('\n'.join(str(T) for T in GoPoint))

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

using namespace std;
 
typedef long long ll;

#define MP make_pair
#define F first
#define S second

int main(){
	ll n;
    cin >> n;
    ll a[n],b[n],c[n];
    for(ll i=0;i<n;i++){
    	cin >> a[i];
    }
    for(ll i=0;i<n;i++){
    	cin >> b[i];
    }
    for(ll i=0;i<n;i++){
    	cin >> c[i];
    }
    sort(a,a+n);
	sort(b,b+n);
    sort(c,c+n);
    ll ans=0;
    for(ll i=0;i<n;i++){
    	ll ok=-1; //a二分
        ll ng=n;
        while(abs(ok-ng)>1){
        	int mid=(ok+ng)/2;
          	if(a[mid]<b[i]){ ok=mid;}else{ng = mid;}
        }
        ll tmp= ok+1;
        ng=-1; //b二分
        ok=n;
        while(abs(ok-ng)>1){
        	int mid=(ok+ng)/2;
          	if(b[i]<c[mid]){ ok=mid;}else{ng = mid;}
        }
        ans +=tmp*(n-ok);
    }
    cout << ans << endl;
}

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

#define pi 3.141592653589
#define MOD 1000000007
#define to() int t; cin>>t; while(t--)
#define pb push_back
#define in insert
#define mp make_pair
#define ff first
#define ss second
#define si(s) s.size()
#define fori(it,v) for(it=v.begin();it!=v.end(); it++)
#define for1(low,high,k) for(int i=low;i<high;i+=k)
#define for11(low,high,k) for(int j=low;j<high;j+=k)
#define for2(low,high,k) for(int i=low;i<=high;i+=k)
#define rev(high,low,k)  for(int i=high;i>=low ;i-=k)
#define all(x) x.begin(), x.end()
#define fil(x,i) memset(x,i,sizeof(x));
#define setbits(x) __builtin_popcount(x)
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

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

int main()
{
	boost; i_o();
	string s; cin >> s;
	int n = s.size();
	if (s[n - 1] == 's') s += "es";
	else s += "s";
	cout << s << endl;
	return 0;
}


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

long long patty_num(const int l,
                    const long long x,
                    const vector<long long>& patty,
                    const vector<long long>& bun,
                    const vector<long long>& all){
  if(l == 0){
    if(x <= 0){
      return 0;
    }else{
      return 1;
    }
  }

  if(x <= 1){
    return 0;
  }

  if(x >= all[l]){
    return patty[l];
  }

  long long ret =
    patty_num(l - 1, x - 1, patty, bun, all) +
    patty_num(l - 1, x - (1 + all[l - 1] + 1), patty, bun, all);
  if(x >= 1 + all[l - 1] + 1){
    ret += 1;
  }
  return ret;
}

int main(){
  int N;
  long long X;
  cin >> N >> X;

  vector<long long> all(N + 1), patty(N + 1), bun(N + 1);
  patty[0] = 1;
  all[0] = 1;
  for(int n = 1; n <= N; n++){
    patty[n] = 2 * patty[n - 1] + 1;
    bun[n] = 2 * bun[n - 1] + 2;
    all[n] = patty[n] + bun[n];
  }

  long long ans = patty_num(N, X, patty, bun, all);
  cout << ans << endl;

}


Measured memory_bytes: 888
n,*t=map(int,open(0).read().split());A=t[:n];B=t[n:];r=0
while 1:
 c=0
 for i in range(n):
  b=B[~-i%n]+B[-~i%n]
  if 0<b<B[i] and A[i]<B[i]:t=(B[i]-A[i])//b;c+=t;B[i]-=t*b
 r+=c
 if c==0:break
print([-1,r][A==B])

Measured memory_bytes: 126804
#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;

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int ans[101010];
int X[101010], Y[101010], Z[101010];

vector<int> g[101010];
void solve(int u) {
    for (int v : g[u]) {
        if (ans[v] != -1) continue;
        ans[v] = 2;
        solve(v);
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    fill(ans, ans+N, -1);
    map<int, int> used;
    rep(i, M) {
        cin >> X[i] >> Y[i] >> Z[i];
        X[i]--; Y[i]--;
        used[X[i]]++;
        used[Y[i]]++;
        // if (Z[i]%2 == 0) {
        //     ans[X[i]] = ans[Y[i]] = 1;
        // }
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    vector<pair<int, int>> tmp;
    rep(i, N) {
        tmp.emplace_back(used[i], i);
    }
    sort(tmp.rbegin(), tmp.rend());

    // rep(i, 20) {
    //     rep(j, M) {
    //         if (Z[j]%2) {
    //             if (ans[X[j]] == -1 and ans[Y[j]] == -1) continue;
    //             else if (ans[X[j]] != -1 and ans[Y[j]] == -1) {
    //                 if (ans[X[j]] == 0) {
    //                     ans[Y[j]] = 1;
    //                 }
    //             }
    //             else if (ans[X[j]] == -1 and ans[Y[j]] != -1) {
    //                 if (ans[Y[j]] == 0) {
    //                     ans[X[j]] = 1;
    //                 }
    //             }
    //         }
    //     }
    // }

    int ret = 0;
    rep(i, N) {
        int v = tmp[i].second;
        if (ans[v] == -1) {
            ret++;
            ans[v] = 2;
            solve(v);
        }
    }

    cout << ret << endl;

}


Measured memory_bytes: 15992
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

ll n;
ll a[1000005];
ll b[1000005];
ll x = 0;

ll f(ll p)
{
    if(p <= 1) return 0;
    return p / 2 + f(p / 2);
}

int main()
{
    scanf("%lld", &n);
    for(ll i = 0; i < n; i++)
    {
        scanf("%1lld", &a[i]);
    }
    for(ll i = 0; i < n - 1; i++)
    {
        b[i] = abs(a[i] - a[i + 1]);
        if(f(n - 2) - f(i) - f(n - i - 2) == 0) x ^= (b[i] % 2);
    }
    if(x == 1)
    {
        printf("1\n");
        return 0;
    }
    for(ll i = 0; i < n - 1; i++)
    {
        if(b[i] == 1)
        {
            printf("0\n");
            return 0;
        }
    }
    x = 0;
    for(ll i = 0; i < n - 1; i++)
    {
        b[i] /= 2;
        if(f(n - 2) - f(i) - f(n - i - 2) == 0) x ^= (b[i] % 2);
    }
    if(x == 1)
    {
        printf("2\n");
    }
    else
    {
        printf("0\n");
    }
    return 0;
}


Measured memory_bytes: 15872
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if i < 10 and n % i == 0:
            if n//i < 10:
                divisors.append([i, n//i])
            # if i != n // i:
            #     divisors.append(n//i)

    # divisors.sort()
    return divisors


N = int(input())

div = make_divisors(N)
div2 = [True if i[0] < 10 and i[1]  < 10 else False for i in div]

if div and all(div):
    print('Yes')
else:
    print('No')





Measured memory_bytes: 3060
using System;

namespace ABC106C
{
    class MainClass
    {
        public static void Main(string[] args)
        {

            // N M みたいな入力
            string Sinput = Console.ReadLine();
            char[] S = Sinput.ToCharArray();

            // N M みたいな入力
            string input2 = Console.ReadLine();
            long K = long.Parse(input2);

            //5000兆
            long n = 5000000000000000;

            //ans
            int ans = 0;
            double p = 0;
            for (int i = 0; i < S.Length;i++){
                p = Math.Pow(double.Parse(S[i].ToString()), n);
                if(p>=K){
                    ans = int.Parse(S[i].ToString());
                    break;
                }else{
                    K =  K - (long)p;
                    //Console.WriteLine(K);
                }

            }


            //出力
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<int, int>;

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

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int ans[3][3];

bool check() {
  // たて、横、斜めの和をsetに入れていき、最終的にサイズが1ならOK
  set<int> st;
  int sum;
  for (int i = 0; i < 3; i++) {
    sum = 0;
    for (int j = 0; j < 3; j++) {
      sum += ans[i][j];
    }
    st.insert(sum);
  }
  for (int i = 0; i < 3; i++) {
    sum = 0;
    for (int j = 0; j < 3; j++) {
      sum += ans[j][i];
    }
    st.insert(sum);
  }
  sum = 0;
  for (int i = 0, j = 0; i < 3; i++, j++) {
    sum += ans[i][j];
  }
  st.insert(sum);
  sum = 0;
  for (int i = 2, j = 0; i >= 0; i--, j++) {
    sum += ans[i][j];
  }
  st.insert(sum);

  return st.size() == 1;
}

int main() {
  // 入力
  int A, B, C;
  cin >> A >> B >> C;

  // 総和として0〜300の候補があるので、全探索
  ans[0][0] = A;
  ans[0][1] = B;
  ans[1][1] = C;
  for (int s = 0; s <= 300; s++) {
    ans[0][2] = s - (A + B);
    ans[2][1] = s - (B + C);
    ans[2][2] = s - (A + C);
    ans[1][2] = s - (ans[0][2] + ans[2][2]);
    ans[2][0] = s - (ans[0][2] + ans[1][1]);
    ans[1][0] = s - (ans[1][1] + ans[1][2]);

    if (check()) break;
  }

  // 解答
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      cout << ans[i][j];
      if (j < 2) cout << " ";
    }
    cout << endl;
  }

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
      
      String S = sc.next();
      
      if(S.equals("AAA")||S.equals("BBB")){
      System.out.println("No");
      }
      else {
      System.out.println("Yes");
      }
    }
}

Measured memory_bytes: 22868
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long  INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;
int N, M;
vector<int> X, L;
void solve() {
    cin >> N >> M;
    X.resize(M);
    L.resize(M - 1);
    for (int i = 0; i < M; i++) {
        cin >> X[i];
    }
    sort(X.begin(), X.end());
    for (int i = 0; i < (M - 1); i++) {
        L[i] = X[i + 1] - X[i];
    }
    sort(L.begin(), L.end());
    int ans = 0;
    for (int i =  (L.size()  - 1) - (N - 1); i > -1; i--) {
        ans += L[i];
    }
    cout << ans << endl;
    return;
}
//逆元を求める関数
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
      fac[i] = fac[i-1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
      finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
//組み合わせ
long long COM (int n, int k) {
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}
int main(int args, char* argv[]) {
    solve();
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstring>
#include <cstdio>

#define LL long long

using namespace std;

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

LL n, k;

int main() {
    n = read(); k = read();
    n %= k;
    cout << min(n, k - n) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100010;
int a[MAXN],n,cnt,h,w,b[MAXN];
int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
int main(){
    cin>>n>>h>>w;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++){
        if(a[i]>=h&&b[i]>=w) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

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

def gcd(a,b):
    if b==0:return a
    return gcd(b, a%b)

L = A.copy()
R = A.copy()
for i in range(1, N):
    L[i] = gcd(L[i-1], L[i])

for i in reversed(range(0, N-1)):
    R[i] = gcd(R[i+1], R[i])

result = max(R[1],L[-2])

for i in range(1, N-1):
    result = max(result, gcd(L[i-1],R[i+1]))
print(result)


Measured memory_bytes: 14584
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;

    int cnt = 0;
    while (b <= a) {
        b *= 2;
        cnt++;
    }
    while (c <= b) {
        c *= 2;
        cnt++;
    }

    if (cnt <= k) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3636
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    H, N = map(int, input().split())
    magic = [list(map(int, input().split())) for _ in range(N)]
    dp = [float("inf") for _ in range(H + 1)]
    dp[0] = 0

    for h in range(H):
        for m in magic:
            a, b = m[0], m[1]
            tmp = dp[h] + b
            if h + a >= H and tmp < dp[H]:
                dp[H] = tmp
            elif h + a < H and tmp < dp[h + a]:
                dp[h + a] = tmp
    print(dp[-1])


if __name__ == "__main__":
    main()


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

unsigned long long xor128() {
    static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
    unsigned long long rt = (rx ^ (rx << 11));
    rx = ry;
    ry = rz;
    rz = rw;
    return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}

std::chrono::system_clock::time_point start;
std::chrono::system_clock::time_point owari;

bool A[3003][3003];
int T[3003];
int n,m,k,MIN=1e9,cnt[3003];

int main(){
    start = std::chrono::system_clock::now();
    cin>>n>>m>>k;
    r(i,m){
        int a,b;
        cin>>a>>b; a--; b--;
        A[a][b]=A[b][a]=1;
        cnt[a]++;
        cnt[b]++;
    }
    r(i,n)T[i]=cnt[i];
    for(;;){
        int TEMP=0;
        for(;;){
            int x,idx=-1,MAX=0;
            r(i,n){
                if(MAX<cnt[i]||(cnt[i]&&(xor128()%114514==810))){
                    MAX=cnt[i];
                    x=i;
                }
                if(cnt[i]==1) idx=i;
            }
            if(!MAX)break;
            TEMP++;
            if(idx!=-1){
                r(i,n)if(A[idx][i]&&cnt[i]){
                    x=i;
                    break;
                }
            }
            r(i,n)if(A[x][i]&&cnt[i])cnt[i]--;
            cnt[x]=0;
        }
        MIN=min(TEMP,MIN);
        owari = std::chrono::system_clock::now();
        double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(owari-start).count();
        if(elapsed>0.1)break;

        r(i,n)cnt[i]=T[i];

    }
    if(MIN<=k)cout<<MIN<<endl;
    else cout<<"Impossible"<<endl;
}


Measured memory_bytes: 11920
s=input()
N=len(s)

ind_a=0
ind_z=0
for i in range(N):
    if s[i]=="A":
        ind_a=i
        break
for i in range(1,N+1):
    if s[-i]=="Z":
        ind_z=N-i
        break

print(ind_z-ind_a+1)

Measured memory_bytes: 9208
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
} 
   
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	T=1;
	while(T--)
	{
		int n;
		cin>>n;
		ll a[n];
		cin>>a[0];
		ll mx=a[0];
		ll ans=0;
		for(int i=1;i<n;i++)
		{
			cin>>a[i];
			if(a[i]<mx)
			{
				ans+=mx-a[i];
			}
			else
			{
				mx=a[i];
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Measured memory_bytes: 5180
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,n) for ( int i = (a); i < (n); ++i)
#define REP(i,n) for( int i = 0; i < (n); ++i )
#define ALL(obj) (obj).begin(), (obj).end()

int64_t com( int64_t n, int64_t r)
{
    if( r < 0 || r > n ) return 0;
    else if( r == 0 ) return 1;
    else if( r == 1 ) return n;
    else if( r == 2 ) return (n*(n-1))/2;
    return (n*(n-1)*(n-2)) / 6;
}

int64_t lpow( long long N, long long K) 
{
    long long res = 1;
    for (int i = 0; i < K; ++i) res *= N;
    return res;
}

int64_t solve( int T, int N, int K )
{
    int64_t count = 0;

    if( T == 0 ) return 0;
    // 0xxxx
    count += com( N-1, K ) * lpow( 9, K );

    // 1xxxx ~ (T-1)xxxx
    count += com( N-1, K-1) * lpow( 9, K-1 ) * (T-1);

    return count;
}

int main()
{
    string S;
    int K;
    cin >> S;
    cin >> K;
    int N = S.size();

    int64_t count = 0;
    int idx = 0;

    if( N >= K ) {
        REP(m,K) {
            while( S[idx] == '0' && idx < N ) {
                idx++;
            }
            if ( idx >= N ) {
                break;
            }
            count += solve( S[idx] - '0', N - idx, K - m );
            if( m == K - 1 ) {
                count++;
            }
            idx++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define hi(x) ((x)>>16)
#define lo(x) ((x)&0xffff)

struct comp{
    bool operator()(const unsigned a, const unsigned b){return hi(a)*lo(a) < hi(b)*lo(b);}
};

int main(){
	int n,w,d;
	while(1){
		scanf("%d %d %d",&n,&w,&d);
		if(!n&&!w&&!d)return 0;
		
{
	vector<unsigned> v;
	v.push_back((w<<16)+d);
	while(n--){
		int p, s, state=0;
		scanf("%d %d", &p, &s);
		p--;
		s%=(hi(v.at(p))+lo(v.at(p)));
		
		unsigned x=hi(v.at(p)), y=lo(v.at(p)), _x=0, _y=0;
		while(s--){
			switch(state){
				case 0:{
					_x++;
					if(_x==x)state=1;
					break;
				}
				case 1:{
					_y++;
					break;
				}
			}
		}
		unsigned x1, x2, y1, y2;
		switch(state){
			case 0:{
				x1=_x;x2=x-_x;
				y1=y2=y;
				break;
			}
			case 1:{
				x1=x2=x;
				y1=_y;y2=y-_y;
				break;
			}
		}
		
		v.erase(v.begin()+p);
		if(x1*y1>x2*y2){
			v.push_back((x2<<16)+y2);
			v.push_back((x1<<16)+y1);
		}else{
			v.push_back((x1<<16)+y1);
			v.push_back((x2<<16)+y2);
		}
	}
	
	sort(v.begin(), v.end(), comp());
	while(v.size()){
		printf("%d", hi(v.at(0))*lo(v.at(0)));
		v.erase(v.begin());
		if(v.size())printf(" ");
	}
	printf("\n");
}
	}
}

Measured memory_bytes: 0
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    s = input()
    ans = 0
    for i in s:
        if i == '1':
            ans += 1
    
    print(ans)

solve()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
typedef long long ll;

using namespace std;

#define REP(i,a,b) for (int i = a; i <= b; i++)
#define ALL(a)              a.begin(), a.end()
#define ALLN(a, n)          (a, a+n)
#define MAX                 10000007
#define MIN                 -10000007



              
int main()
{
  ios::sync_with_stdio(0);
    cin.tie(0);
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
      
    int t;
    t=1;
     //  cin>>t;
    while(t--){
        	ll n,k;
        	cin>>n>>k;
        	ll a[n+1];
        	REP(i,1,n){cin>>a[i];}
        	REP(i,k+1,n){
        		if(a[i-k]<a[i])cout<<"Yes"<<"\n";
        		else cout<<"No"<<"\n";
        	}
       


             }
             cerr<<"Time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
    return 0;
}


Measured memory_bytes: 5264
using System;
using System.Collections.Generic;
using System.Linq;

class D
{
	struct P
	{
		public int i, j;
		public P(int _i, int _j) { i = _i; j = _j; }
		public bool IsInRange => 0 <= i && i < h && 0 <= j && j < w;
		public P[] Nexts() => new[] { new P(i, j - 1), new P(i, j + 1), new P(i - 1, j), new P(i + 1, j) };
	}

	static int h, w;
	static string[] c;

	static void Main()
	{
		Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
		var z = read();
		h = z[0]; w = z[1];
		c = new int[h].Select(_ => Console.ReadLine()).ToArray();

		var sp = new P();
		var gp = new P(h - 1, w - 1);
		var r = Search(sp, gp);
		Console.WriteLine(r == -1 ? -1 : h * w - r - 1 - c.Sum(s => s.Count(x => x == '#')));
	}

	static int Search(P sp, P gp)
	{
		var u = new int[h, w];
		var q = new Queue<P>();
		u[sp.i, sp.j] = 1;
		q.Enqueue(sp);

		while (q.Any())
		{
			var p = q.Dequeue();
			foreach (var x in p.Nexts())
			{
				if (!x.IsInRange || u[x.i, x.j] > 0 || c[x.i][x.j] == '#') continue;
				u[x.i, x.j] = u[p.i, p.j] + 1;
				q.Enqueue(x);
			}
		}
		return u[gp.i, gp.j] - 1;
	}
}


Measured memory_bytes: 13524
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

int n, m;
// string s;

int main() {
    cin >> n >> m;
    Vi a(m);
    REP(i, m) cin >> a[i];

    Vi need = {-1, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
    auto func = [](string &l, string &r) {
        if (l.size() == r.size()) return l < r;
        return l.size() < r.size();
    };

    V<Vs> dp(n+1, Vs(m, "x"));
    REP(i, m) dp[0][i] = "";
    REP2(i, 1, n+1) {
        REP(j, m) {
            if (i < need[a[j]]) continue;
            Vs v;
            REP(k, m) {
                string s = dp[i-need[a[j]]][k];
                if (s == "x") continue;
                string t = s.insert(
                    lower_bound(ALL(s), '0' + a[j], greater<char>()) - s.begin(),
                    to_string(a[j])
                );
                v.push_back(t);
            }
            if (v.empty()) continue;
            sort(ALL(v), func);
            dp[i][j] = v.back();
        }
    }
    Vs res;
    for (auto x: dp[n]) {
        if (x != "x") res.push_back(x);
    }
    cout << *max_element(ALL(res), func) << '\n';

    return 0;
}


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

using namespace std;

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

  int n;
  string prev, w;
  set<string> store;
  cin >> n >> prev;
  n--;
  string res = "Yes";
  while (n--) {
    store.insert(prev);
    cin >> w;
    if (w[0] != prev[prev.size()-1] || store.find(w) != store.end()) {
      res = "No";
      break;
    }
    prev = w;
  }
  cout << res << endl;

  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int main() {
  string s;
  cin>>s;
  int n = s.size();
  char last = s[n-1];
  bool cando = true;
  string sub, sub2;
  while(s.length() >= 5) {
    if(last == 'm') {
      //eat dream
      sub = s.substr(n-5, 5);
      if(sub != "dream") {
        cando=false;
        break;
      }
      s = s.substr(0, n-5);
    } else if(last == 'r') {
      //eat dreamer or eraser
      sub = n >= 6 ? s.substr(n-6, 6) :"";
      sub2 = n >= 7 ? s.substr(n-7, 7) : "";
      if(sub == "eraser") {
        s = s.substr(0, n-6);
      } else if(sub2 == "dreamer") {
        s = s.substr(0, n-7);
      } else {
        cando=false;
        break;
      }
    } else if(last == 'e') {
      //eat erase
      sub = s.substr(n-5, 5);
      if(sub != "erase") {
        cando=false;
        break;
      }
      s = s.substr(0, n-5);
    } else {
      cando=false;
      break;
    }
    n = s.length();
    if(n>=5) last = s[n-1];
  }
  if(s.length() == 0 && cando==true) cout << "YES";
  else cout << "NO";
  cout<<endl;
  return 0;
}


Measured memory_bytes: 596
#include<stdio.h>
int main ()
{
    int a,b,c,x,z;
    
    z = 0;
    
    scanf("%d %d %d",&a,&b,&c);
    for (x = a;x <= b;x++){
        
        if (c % x == 0){
            z++;
        }
         
    }
    printf("%d\n",z);
    return 0;
}


Measured memory_bytes: 2108
S=input()
X=[]
SS=""
cnt=0
for s in S:
    if s!='x':
        SS+=s
        X.append(cnt)
        cnt=0
    else:
        cnt+=1
X.append(cnt)
flag=True
for i in range(len(SS)//2):
    if SS[i]!=SS[-1-i]:
        flag=False
ans=0
for i in range(len(X)//2):
    ans+=abs(X[i]-X[-1-i])
if flag:
    print(ans)
else:
    print(-1)

Measured memory_bytes: 3988
N, M = [int(n) for n in input().split(' ')]
WA = {}
AC = {}
for i in range(M):
    p, S = [n for n in input().split(' ')]
    if p not in WA:
        WA[p] = 0
    if S == "WA":
        WA[p] += 1
    else:
        if p not in AC: 
            AC[p] = WA.pop(p)
print(len(AC), sum(AC.values()))
        
    

Measured memory_bytes: 59992
n, k = map(int, input().split())
d = []
a = []
for i in range(k):
    d.append(int(input()))
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)):
        a.append(tmp[j])

setc = set(a)
print(n - len(setc))

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

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int > vi;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
 
#define ALL(x) (x).begin(), (x).end()
#define RESET(x) memset((x), 0, sizeof (x))
#define FOR(i, b, e) for ( int i = (b); i < (e); ++i)
#define RE(i, n) FOR(i, 0, (n))
#define FOREACH(i, x, y) for ( int i = (x); i <= (y); ++i)
#define two(X) (1<<(X))//NOTES:two(
#define contain(S,X) (((S)&two(X))!=0)//NOTES:contain(
#define chkmin(X, Y) (X) = min((X), (Y))
#define chkmax(X, Y) (X) = max((X), (Y))
#define sqr(X) ((X) * (X))
#define MP(x, y) make_pair((x), (y))
 
const int LOGN = 22;
const ll INF = (1 << 30) + 10;
const ll MOD = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = 1e-12;

const long long maxn = 1e5 + 100;
const ll maxm = (ll) 1e6;

int main() {
#ifndef ONLINE_JUDGE
   // freopen("in.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;
    while (cin >> n) {
        vi a(n);
        RE(i, n) cin >> a[i];
        ll v = 0;
        ll ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (v == a[i]) {
                --v;
                chkmax(v, 0LL);
                continue;
            }
            if (a[i] > i || v > a[i]) {
                ans = -1;
                break;
            }
            ans += a[i];
            v = a[i] - 1;
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;
void printVec(std::vector<int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}

int main() {
	int N; cin >> N;
	int maxx = 0;
	vector<int> a(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		maxx = max(maxx, a[i]);
	}
	vector<int> b(a);
	std::sort(b.begin(), b.end(), std::greater<int>());//降順ソート

	for (int i = 0; i < N; i++) {
		if (a[i] == maxx) {
			cout << b[1] << endl;

		}
		else {
			cout << maxx << endl;
		}


	}



	//printVec(counts);

	return 0;
}

Measured memory_bytes: 3200
temp = input()
a,b,c = temp.split()
a = int(a)
b = int(b)
c = int(c)
inp = [a,b,c]
inp = sorted(inp)
dif = inp[2] - inp[0] + inp[2] - inp[1]

if dif%2 == 0:
    print(dif//2)
else:
    print((dif+3)//2)


Measured memory_bytes: 3060
n = int(input())
A = []
B = []
C = []
for _ in range(n):
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
dp = [[0]*3 for i in range(n)]
dp[0][0] = A[0]
dp[0][1] = B[0]
dp[0][2] = C[0]
for i in range(1,n):
    dp[i][0] = max(dp[i-1][1]+A[i],dp[i-1][2]+A[i])
    dp[i][1] = max(dp[i-1][0]+B[i],dp[i-1][2]+B[i])
    dp[i][2] = max(dp[i-1][0]+C[i],dp[i-1][1]+C[i])
print(max(dp[-1]))

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

using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define pb(a) push_back(a)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

int main(){
	int r,g,b,n;
	cin >> r >> g >> b >> n;
	int c=0;
	REP(i,n+1){
		if(r*i<=n){
			REP(j,n+1){
				if(r*i+g*j<=n){
					if((n-r*i-g*j)%b==0){
						c++;
					}
				}
			}
		}
	}
	cout << c <<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define INF 1e9

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
	string s;
	cin >> s;
	s[5] = s[13] = ' ';
	cout << s << endl;
}

Measured memory_bytes: 256
#include <cstdio>

int main()
{
  char s[3][101];
  scanf("%s %s %s", s[0], s[1], s[2]);
  int w = 0;
  int c[3] = {0, 0, 0};
  while (s[w][c[w]] != 0)
  {
    int next = s[w][c[w]++] - 'a';
    w = next;
  }
  printf("%c\n", w + 'A');
  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

int main(void)
{
	int K = 0, U = 0, P = 0, C = 0;
	char str[512];
	int i, min = 301;
	
	scanf("%s", str);
	
	i = 0;
	while (str[i] != '\0'){
		switch (str[i]){
			case 'K':
			K++;
			break;
			
			case 'U':
			U++;
			break;
			
			case 'P':
			P++;
			break;
			
			case 'C':
			C++;
			break;
		}
		i++;
	}
	
	if (min > K) min = K;
	if (min > U) min = U;
	if (min > P) min = P;
	if (min > C) min = C;
	
	printf("%d\n", min);
	
	return (0);
}

Measured memory_bytes: 536
#include<cstdio>
#include<vector>
#include<cstring>
#include<utility>
using namespace std;
int n;
vector< pair<int,int> > v[111111];
int dist[111111];
void dfs(int x)
{
	for(int i=0;i<v[x].size();i++)
	{
		int p=v[x][i].first,q=v[x][i].second;
		if(dist[p]==-1)
		{
			dist[p]=dist[x]+q;
			dfs(p);
		}
	}
}
int main()
{
	memset(dist,-1,sizeof(dist));
	scanf("%d",&n);
	dist[1]=0;
	for(int i=1;i<n;i++)
	{
		int u,V,w;
		scanf("%d %d %d",&u,&V,&w);
		v[u].push_back(make_pair(V,w%2+2));
		v[V].push_back(make_pair(u,w%2+2));
	}
	dfs(1);
	for(int i=1;i<=n;i++) printf("%d\n",dist[i]%2);
}

Measured memory_bytes: 8704
#include <iostream>

unsigned gaps[] = {1,8,23,77,281,1073,4193,16577,65921,262913};
// generated from pow(4,i)+3*pow(2,i-1)+1 (prefixed with 1)

unsigned insertion_sort(unsigned a[], unsigned n, unsigned gap){
  unsigned count = 0;
  for(unsigned i = gap; i < n; i++){
    unsigned v = a[i];
    int j = i - gap;
    while(j >= 0 && a[j] > v){
      a[j+gap] = a[j];
      j -= gap;
      count++;
    }
    a[j+gap] = v;
  }
  return count;
}

void shell_sort(unsigned a[], unsigned n){
  unsigned gap_num = 0;
  while(gaps[++gap_num] < n);
  gap_num--;

  unsigned count = 0;
  for(int i = gap_num; i >= 0; i--) count += insertion_sort(a,n,gaps[i]);

  std::cout << (gap_num+1) << '\n';

  for(int i = gap_num; i; i--) std::cout << gaps[i] << ' ';
  std::cout << gaps[0] << '\n';

  std::cout << count << '\n';
}

int main(){
  std::ios::sync_with_stdio(false);
  unsigned n;
  unsigned a[1000000];
  std::cin >> n;
  for(unsigned i = 0; i < n; i++) std::cin >> a[i];
  shell_sort(a,n);
  for(unsigned i = 0; i < n; i++) std::cout << a[i] << '\n';
}

Measured memory_bytes: 5100
import java.util.*;
public class Main {
    public static void main (String[] args) {
      Scanner sc = new Scanner(System.in);
      String str = sc.next();
      char[] array = str.toCharArray();
      Arrays.sort(array);
      String sortedStr = new String(array);
      String ans = (sortedStr.equals("abc"))? "Yes" : "No";
      
      System.out.println(ans);
    }
}

Measured memory_bytes: 35620
import sys
 
stdin = sys.stdin

N,Q = map(int,input().split())
S = input()
se = [list(map(int, stdin.readline().split())) for i in range(Q)]

list_out = [0] * N
cnt = 0
f = 0

# AC文字列のAの位置をリストに収めた
for i in range(len(S)):
  if S[i] == 'A':
    f = 1
    list_out[i] = list_out[i-1]    
  elif S[i] == 'C':
    if f == 1:
      cnt += 1
      f = 0
      list_out[i] = cnt
    else:
      list_out[i] = list_out[i-1]
  else:
    f = 0
    list_out[i] = list_out[i-1]    


# 指定した文字列範囲を含む要素数を表示
for i in se:
  print(list_out[i[1]-1] - list_out[i[0]-1])


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    string S;
    cin >> S;

    ll N = S.length();

    if(S[N-1] == '2'){
        cout << "hon" << endl;
    }
    if(S[N-1] == '4'){
        cout << "hon" << endl;
    }
    if(S[N-1] == '5'){
        cout << "hon" << endl;
    }
    if(S[N-1] == '7'){
        cout << "hon" << endl;
    }
    if(S[N-1] == '9'){
        cout << "hon" << endl;
    }

    if(S[N-1] == '0'){
        cout << "pon" << endl;
    }
    if(S[N-1] == '1'){
        cout << "pon" << endl;
    }
    if(S[N-1] == '6'){
        cout << "pon" << endl;
    }
    if(S[N-1] == '8'){
        cout << "pon" << endl;
    }

    if(S[N-1] == '3'){
        cout << "bon" << endl;
    }
    return 0;
}

Measured memory_bytes: 3644