akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder200531
{
    class Program
    {
        static void Main(string[] args)
        {
            //int n = int.Parse(Console.ReadLine());
            List<int> inputs = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToList();
            List<int> nums = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToList();
            //char[] input = Console.ReadLine().ToCharArray();

            nums.Sort();
            int sum = 0;
            for(int i = 0; i < inputs[1]; i++)
            {
                sum += nums[i];
            }

            Console.WriteLine(""+sum);
        }
    }
}


Measured memory_bytes: 28656
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "}"; return os; }


// 素因数分解
map<LL,LL> factorize(LL val){
    assert(val > 0);
    map<LL,LL> factor;
    for(LL p = 2; p*p <= val; ++p){
        while(val % p == 0){
            ++factor[p];
            val /= p;
        }
    }
    if(val > 1) ++factor[val];
    return factor;
}


int main(){
    LL n;
    cin >> n;
    map<LL,LL> f = factorize(n);
    LL ans = 0;
    for(auto p: f){
        LL cnt = 1;
        while(p.second >= cnt){
            ans += 1;
            p.second -= cnt;
            cnt += 1;
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3196
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) cout << fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

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

    ll n, m;
	cin >> n >> m;
	vector<vll> v(m, vll(0));
	for (ll i = 0; i < n; i++) {
		ll a, b;
		cin >> a >> b;
		if (a <= m) v[m - a].push_back(b);
	}
	priority_queue<ll> pq;
	ll ans = 0;
	for (ll i = 0; i < m; i++) {
		for (ll j = 0; j < v[m - 1 - i].size(); j++) pq.push(v[m - 1 - i][j]);
		if (pq.size()) {
			ans += pq.top();
			pq.pop();
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 5632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int n,k;
  cin>>n>>k;
  vector<int> fu;
  vector<int> sei;
  sei.push_back(0);
  rep(i,0,n){
    int x;
    cin>>x;
    if(x<0) fu.push_back(-x);
    else sei.push_back(x);
  }
  fu.push_back(0);
  reverse(fu.begin(),fu.end());
  
  int ans=1e9;
  rep(i,0,fu.size()){
    if(i+sei.size()-1<k) continue;
    if(i>k) break;
    ans=min(ans,2*fu[i]+sei[k-i]);
  }
  rep(i,0,sei.size()){
    if(i+fu.size()-1<k) continue;
    if(i>k) break;
    ans=min(ans,2*sei[i]+fu[k-i]);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1020
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <list>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 最大公約数
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;
}*/

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n;
	cin >> n;
	string s;
	cin >> s;

	// ( の数 == ) の数としたい
	// このときの辞書順最小とは・・・？
	// ( のほうが辞書順で小さいのかも
	// 足りない分を足してあげる
	// 一番左に( を追加しまくるのが一番辞書順で小さくなる

	// 解が正しくなる条件は？
	// ( ) の間に ( もしくは ) だけが入らない
	// もしかして間に挿入することはない？
	int leftNum = 0;
	int rightNum = 0;

	rep(i, n) {
		if (s[i] == '(') leftNum++;
		else if (leftNum >= 1)leftNum--;
		else rightNum++;
	}

	rep(i, rightNum) cout << '(';
	cout << s;
	rep(i, leftNum) cout << ')';
	cout << endl;
}


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

using namespace std;

int main() {
  int N, Q;
  cin >> N >> Q;
  vector<char> s(N + 1);
  vector<int> t(N);
  scanf("%s", s.data());

  int count = 0;
  for (int i = 0; i < N - 1; i++) {
    if (s[i] == 'A' && s[i + 1] == 'C') {
      t[i] = count++;
      t[i + 1] = count;
    } else {
      t[i] = count;
    }
  }

  t[N - 1] = count;

  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    cout << t[r - 1] - t[l - 1] << endl;
  }
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
P x[100009],y[1000009];

int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    if(i%2==0)x[a].first++;
    else y[a].first++;
  }
  for(int i=1;i<=100000;i++){
    x[i].second=i;
    y[i].second=i;
  }
  sort(x,x+100000);
  sort(y,y+100000);
  reverse(x,x+100000);
  reverse(y,y+100000);
  int s=0,t=0;
  if(x[0].second==y[0].second){
    if(x[0].first+y[1].first>x[1].first+y[0].first){
      cout<<n-x[0].first-y[1].first<<endl;
    }
    else cout<<n-x[1].first-y[0].first<<endl;
  }
  else{
    cout<<n-x[0].first-y[0].first<<endl;
  }
  return(0);
}


Measured memory_bytes: 8960
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

int main(){
    int x,y;
    while(cin >> x >> y,x || y){
        if(x > y) cout << y << " " << x << endl;
        else cout << x << " " << y << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
const ll MOD = 1e9;

int main(){
  string s;
  cin>>s;
  int f=0;
  if(s=="KIHBR")f=1;
  if(s=="KIHBRA")f=1;
  if(s=="KIHBAR")f=1;
  if(s=="KIHBARA")f=1;
  if(s=="KIHABR")f=1;
  if(s=="KIHABRA")f=1;
  if(s=="KIHABAR")f=1;
  if(s=="KIHABARA")f=1;
  if(s=="AKIHBR")f=1;
  if(s=="AKIHBRA")f=1;
  if(s=="AKIHBAR")f=1;
  if(s=="AKIHBARA")f=1;
  if(s=="AKIHABR")f=1;
  if(s=="AKIHABRA")f=1;
  if(s=="AKIHABAR")f=1;
  if(s=="AKIHABARA")f=1;
  cout<<(f?"YES":"NO")<<endl;
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define zy 2333333
#define bql 2147483647
using namespace std;
int n,ans,a[25],b[25],c[25];
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	   cin>>a[i];
    for (int i=1;i<=n;i++)
       cin>>b[i];
    for (int i=1;i<=n-1;i++)
       cin>>c[i];
    
    for (int i=1;i<=n;i++)
    {
    	ans+=b[a[i]];
    	if (a[i+1]-a[i]==1)
    	   ans+=c[a[i]];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

ll x, y, ans;

ll gcd(ll a, ll b) {
    if (a < b) swap(a, b);

    while (b > 0) {
        a %= b;
        swap(a, b);
    }

    return a;
}

int main()
{
 //   freopen("test.in","r",stdin);

    cin >> x >> y;
    if (x % y == 0) {
        cout << -1;
        return 0;
    }

    ans = (x * y) / gcd(x, y);
    ans -= x;

    cout << ans;


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main()
{
    string s,t;
    int a,b;
    cin>>s>>t>>a>>b;
    string S;
    cin>>S;
    if(S==s)
        a--;
    else
        b--;
    cout<<a<<" "<<b;
    return 0;

}


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if ((A == 5 && B == 5 && C == 7) || (A == 5 && B == 7 && C == 5) || (A == 7 && B == 5 && C == 5))
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

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

std::vector<std::vector<int>> caseList;
int n = 0;
int m = 0;

void dfs(std::vector<int> myCase)
{
    if(myCase.size() == n)
    {
        caseList.push_back(myCase);
        return;
    }
    else if(n < myCase.size())
    {
        return;
    }
    
    int myDigit = myCase[myCase.size() - 1];
    for(int i = myDigit; i <= m; i++)
    {
        std::vector<int> newVect;
        newVect = myCase;
        newVect.push_back(i);
        dfs(newVect);
    }
}

int c()
{
    int q;
    std::cin >> n >> m >> q;
    
    //選ぶやつ列挙
    for(int i = 1; i <= m; i++)
    {
        std::vector<int> cases;
        cases.push_back(i);
        dfs(cases);
    }
    
    std::vector<std::vector<int>> queryList;
    for(int i = 0; i < q; i++)
    {
        int a, b, c, d;
        std::cin >> a >> b >> c >> d;
        std::vector<int> myQuery = {a, b, c, d};
        queryList.push_back(myQuery);
    }
    
    long long maxScore = 0;
    for(int i = 0; i < caseList.size(); i++)
    {
        std::vector<int> myCase = caseList[i];
        long long myScore = 0;
        for(int k = 0; k < q; k++)
        {
            std::vector<int> myQuery = queryList[k];
            int a = myQuery[0];
            int b = myQuery[1];
            int c = myQuery[2];
            int d = myQuery[3];
            
            if(myCase[b - 1] - myCase[a - 1] == c)
            {
                myScore += d;
            }
        }
        if(maxScore < myScore)
        {
            maxScore = myScore;
        }
    }
    
    std::cout << maxScore << std::endl;
    
    return 0;
}

int main(int argc, const char * argv[])
{
    c();
    return 0;
}

Measured memory_bytes: 9868
# include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,k; cin >> n >> k;
  vector<double> p(n,0); for(int i = 0;i < n;i++) { cin >> p[i]; }
  vector<double> e(n,0); for(int i = 0;i < n;i++) { e[i] = (p[i]+1)/2; }
 
  double sum=0,max;
  for(int i = 0;i < k;i++) { sum += e[i]; }
 
  max = sum;
  for(int i = 1;i+(k-1) < n;i++) {
    sum += (e[i+(k-1)] - e[i-1]);
    if(max < sum) { max = sum; }
  }
 
  //cout << max << endl;
  printf("%.2f\n",max);
  return 0;
}

Measured memory_bytes: 3456
from collections import Counter

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

ca = Counter(a)
cb = Counter(b)

for i,j in cb.items():
    if i not in ca or j > ca[i]:
        print("NO")
        exit()
print("YES")

Measured memory_bytes: 57180
# https://atcoder.jp/contests/abc066/tasks/abc066_b

S = input()
S_len = len(S)

while True:
    S = S[:S_len - 2]
    S_len = len(S)

    middle = S_len // 2

    if S[:middle] == S[middle:]:
        print(S_len)
        exit()

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

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

int main(){
    int n;
    scanf("%d", &n);
    map<pii, int> mp;
    rep(_, n){
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        mp[{x, y}] = w;
        rep(i, 4)if(mp.find({x-dx[i], y-dy[i]}) == mp.end()){
            mp[{x-dx[i], y-dy[i]}] = 0;
        }
    }

    int ans = 0;
    for(auto p: mp){
        int x, y, tmp = 0;
        tie(x, y) = p.fi;
        rep(i, 4)if(mp.find({x+dx[i], y+dy[i]}) != mp.end()){
            tmp += mp[{x+dx[i], y+dy[i]}];
        }
        chmax(ans, tmp);
    }
    printf("%d / %d\n", ans, 1);
}


Measured memory_bytes: 28180
#include<stdio.h>

int main() {
	int n,i;
	scanf("%d", &n);
	int a[n];
	for(i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for(i = 0; i < n; i++) {
		printf("%d", a[n-i-1]);
		if(i != n-1) {
			printf(" ");
		}
	}
	printf("\n");
	
	return 0;
}

Measured memory_bytes: 600
def dfs_init(color,n,dq):
	for i in range(n):
		color[i] = "White"

def next(u):
	for v in range(list_next[u],n):
		list_next[u] = v+1
		if list_m[u][v]:
			return v


def dfs_visit(u,color,dq,tt):
	tt = tt
	dq.append(u)
	color[u] = "Gray"
	list_d[u] = tt + 1
	tt += 1
	while dq:
		u = dq[-1]
		v = next(u)
		if v != None:
			if color[v] == "White":
				color[v] = "Gray"
				list_d[v] = tt + 1
				tt += 1
				dq.append(v)
		else:
			dq.pop()
			color[u] = "Black"
			list_f[u] = tt + 1
			tt += 1
	return tt

from collections import deque
n = int(input())
list_m = [[0]*n for i in range(n)]
list_next = [0] * n
list_color = [0] * n
list_d = [0]*n
list_f = [0]*n
dq = deque([])

for i in range(n):
	a,b,*args = map(int, input().split())
	for num in args:
		list_m[a-1][num-1] = 1
tt = 0
list_num = [i+1 for i in range(n)]
dfs_init(list_color,n,dq)
for u in range(n):
	if list_color[u] == "White":
		tt = dfs_visit(u,list_color,dq,tt)

for i in range(n):
	print(list_num[i], list_d[i] ,list_f[i])


Measured memory_bytes: 6128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=1e9+7;
const long double Pi=acos(-1);
using  P=pair<ll,ll>;
int main(){
  ll L,R;
  ll ans=2019;
  cin>>L>>R;
  if(R-L>=2018){cout<<0<<endl;return 0;}
  else{
    for(ll i=L;i<=R-1;i++){
      for(ll j=i+1;j<=R;j++){
        ll a=i%2019;
        ll b=j%2019;
        ll c=(a*b)%2019;
        ans=min(ans,c);
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(v)   ((int)(v).size())
#define  all(v)    ((v).begin()),((v).end())
#define  allr(v)    ((v).rbegin()),((v).rend())
#define   pb         push_back
#define   mp         make_pair
#define    clr(v,d)      memset( v, d ,sizeof(v))
#define     PI                       acos(-1)
typedef  long long     ll ;
typedef  unsigned long long ull;
const double eps= (1e-9);
using namespace std;
int dcmp(long double a,long double b){   return fabsl(a-b)<=eps ? 0: (a>b)? 1:-1  ;}
int getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1;}
int setBit1(int num, int idx) {return num | (1<<idx);}
ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}
ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}
void GO(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
int countNumBit1(int mask) {int ret=0; while (mask) 	{mask &= (mask-1);++ret;	}return ret;}
const int N=100000+9;

int main(){
    GO();

    int T;
  //  cin>>T;
    T=1;
    while(T--){
        int x;
        cin>>x;
        cout<<!x<<"\n";


    }

}





















































































































































































Measured memory_bytes: 3608
#include<stdio.h>
#include<stdlib.h>
int fun(int ,int );
int fun(int A,int N)
{
    while(N%500!=0&&A)
    {
        N--;
        A--;
    }
    if(N%500==0)
    {
        return 1;
    }
    return 0;
}
int main()
{
    int N,A;
    scanf("%d%d",&N,&A);
    printf((fun(A,N)==1)?"Yes\n":"No\n");
    return 0;
}


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int32 n;
  cin >> n;
  ANS(n * (n - 1) / 2);
  return 0;
}

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

using namespace std;

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int l = a + b, r = c + d;
  puts(l > r ? "Left" : (l == r) ? "Balanced" : "Right");
  return 0;
}


Measured memory_bytes: 256
void main()
{
    int n = readln.chomp.to!int;
    int[] a = readln.split.to!(int[]);

    a.sort!"a < b";
    auto g = a.group.array;
    int cnt;
    foreach (x; g)
    {
        if (x[0] > x[1])
        {
            cnt += x[1].to!int;
        }
        else if (x[0] < x[1])
        {
            cnt += x[1].to!int - x[0];
        }
    }

    cnt.writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

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

int main(){

  int N, K, ans=0;
  cin >> N >> K;
  int l[N];
  for(int i=0; i<N; i++){
    cin >> l[i];
  }

  sort(l, l+N, greater<int>());

  for(int i=0; i<K; i++){
    ans += l[i];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;

using namespace std;


int main(int argc, char* argv[])
{    
    int n, k;
    scanf("%d%d", &n, &k);
    vector<pair<int,int> > z;
    int i;
    for(i=0; i<n; i++) {
        int t, d;
        scanf("%d%d", &t, &d);
        z.push_back(make_pair(d, t) );
    }
    sort(z.rbegin(), z.rend());

    vector<pair<int,int> > z0;
    set<int> kind;
    ll pts=0;
    for(i=0; i<k; i++) {
        pts += z[i].first;
        if(!kind.insert(z[i].second).second) {
            z0.push_back(z[i]);    // can be deleted
        }
    }
    reverse( z0.begin(), z0.end() );

    ll val = pts+(ll)kind.size()*kind.size();
    ll max = val;
    if(z0.empty()) {
        printf("%lld\n", max); return 0;
    }

    int id=0;
    for(i=k; i<n; i++) {
        if(kind.insert(z[i].second).second) {
            pts += (z[i].first - z0[id].first);
            id++;
            val = pts+(ll)kind.size()*kind.size();
            max = MAX(max,val);
        }
        if(id==z0.size()) {
            break;
        }
    }
    printf("%lld\n", max);
 

    return 0;
}



Measured memory_bytes: 4340
N, Q = map(int, input().split())
S = input()
l_r_list = [[int(i) for i in input().split()] for _ in range(Q)]

tmp = [0] * N
cnt = 0
for i in range(1, N):
    if S[i-1] + S[i] == 'AC':
        cnt += 1
    tmp[i] = cnt

for l, r in l_r_list:
    print(tmp[r-1] - tmp[l-1])


Measured memory_bytes: 24400
from math import floor

count = 0
n = int(input())

for _ in range(n):
    x = int(input())
    if x == 2 or x == 3:
        count += 1
    for i in range(2, floor(x**(1/2)) + 1):
        if x % i == 0:
            break
        if i == floor(x**(1/2)) and x % i != 0:
            count += 1
            
print(count)


Measured memory_bytes: 5752
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(m)]

ans = []
for i in range(n):
    nearest = 10**9
    idx = None
    for j in range(m):
        a, b = ab[i]
        c, d = cd[j]
        if abs(a-c)+abs(b-d) < nearest:
            nearest = abs(a-c)+abs(b-d)
            idx = j+1
    ans.append(idx)
for i in range(len(ans)):
    print(ans[i])

Measured memory_bytes: 39664
#include<stdio.h>
 int main (){
 	char s[10];
 	 scanf("%s",&s);
 	 if(s[2]==s[3] && s[4]==s[5]){
 	 	printf("Yes");
	}
	else{
		printf("No");
	}
 	
 	return 0;
 }


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

public class Prime{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        //Console.WriteLine("{0}: {1}", n, string.Join(" ", PrimeFactors(n)));
		Console.WriteLine("{0}: {1}", n, string.Join(" ", PrimeFactors(n).Select (x => x.ToString()).ToArray())); //AOJ??¨
    }
     
    public static IEnumerable<int> PrimeFactors(int n)
    {
        int i = 2;
        int tmp = n;
         
        while (i * i <= n)
        {
            if(tmp % i == 0){
                tmp /= i;
                yield return i;
            }else{
                i++;
            }
        }
		if(tmp != 1) yield return tmp;
    }
}

Measured memory_bytes: 20184
#include<bits/stdc++.h>
using namespace std;
int main(){
	bool b=false,ab=false;
	for(int i=0;i<3;i++){
		char a;
		cin>>a;
		if(a=='A'){
			ab=true;
		}else if(a=='B'){
			b=true;
		}
	}
	if(b&&ab){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}

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

using namespace std;

int main(void)
{
    int a, b; cin >> a >> b;
    int total;
    if(a >= 13)
        total = b;
    else if(a <= 5)
        total = 0;
    else
        total = b / 2;
    

    cout << total << endl;
    
    

    return 0;
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

set<lli> yaku(lli num){
    set<lli> rtn;
    for(lli i=1;i*i<=num;i++){
        if(num%i==0){
            rtn.insert(i);
            rtn.insert(num/i);
        }
    }
    return rtn;
}
bool ok(lli n,lli k){
    if(n==1)return true;
    if(n<k)return false;
    if(n%k==0)return ok(n/k,k);
    else return ok(n%k,k);
}

void func(long long N){
    set<lli> y = yaku(N);
    set<lli> yy = yaku(N-1);

    lli cnt=0;

    for(auto e:y){
        if(e==1)continue;
        if(ok(N,e))cnt++;
    }
    for(auto e:yy){
        if(y.find(e)!=y.end())continue;
        if(ok(N,e))cnt++;
    }
    cout<<cnt<<endl;
}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    func(N);
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template <typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template <typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}


int main()
{
    int n,m;
    cin >> n >> m;
    vl x(n), y(m);
    in(n,x);
    in(m,y);
    
    vl xx(n-1),yy(m-1);
    rep(i,n-1) xx[i] = (ll)(i+1)*(ll)(n-1-i);
    rep(i,m-1) yy[i] = (ll)(i+1)*(ll)(m-1-i);
    
    ll sx = 0, sy = 0;
    rep(i,n-1){
        sx += ((x[i+1]-x[i])%mod)*(xx[i])%mod;
        sx %= mod;
    }
    rep(i,m-1){
        sy += ((y[i+1]-y[i])%mod)*(yy[i])%mod;
        sy %= mod;
    }
    
    cout << sx*sy%mod << endl;
    

    
    
    
    

    return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#define int long long

using namespace std;
const int N = 1e5 + 5;

int n, m, v, p;
int a[N], t[N];

bool judge(int x) {
	if (x <= p) return 1;
	if (a[x] + m < a[p]) return 0;
//	if (v <= p - 1 && a[x] + m >= a[p]) return 1;
	for (register int i = 1; i <= n; i++)
		t[i] = a[i];
	for (register int i = 1; i < p; i++)
		t[i] += m;
	
	int cost = m * (p - 1);
	for (register int i = n, c = v - p; i > x && c; c--)
		cost += m, t[--i] += m;
	cost += m;
	
	int left = m * v - cost;
	for (register int i = p; i < x; i++) {
		int inc = min(m, max(a[x] + m - a[i], 0ll));
		inc = min(inc, left);
		left -= inc, t[i] += inc;
	}
	
	return a[x] + m >= t[p] && left <= 0;
}

signed main() {
	cin >> n >> m >> v >> p;
	for (register int i = 1; i <= n; i++)
		cin >> a[i];
	
	sort(a + 1, a + 1 + n, greater<int>());
	
	int l = 1, r = n, ret = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (judge(mid)) ret = mid, l = mid + 1;
		else r = mid - 1;
	}
	
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 5184
#include<cstdio>

int solve(int a,int b){
 
 if(b==4){
  if(a==0) return 1;
  else return 0; 
 }
 else{
  int res=0;
  for(int i=0;i<=a&&i<10;i++){
   res+=solve(a-i,b+1);
  }
  return res;
 }
}

int main(){
 int n;
 while(~scanf("%d",&n)){
  printf("%d\n",solve(n,0));
}
return 0;
}

Measured memory_bytes: 0
// D - String Formation
#include <bits/stdc++.h>
using namespace std;

int main(){
	string F,B; int Q; cin>>B>>Q;
	int odd = 0;
	while(Q--){
		int t; cin>>t;
		if(t==1) odd ^= 1;
		else{
			int f; string c; cin>>f>>c;
			if(odd ^ --f) B += c;
			else F += c;
		}
	}
	if(odd) swap(F,B);
	reverse(F.begin(), F.end());
	cout<< F+B <<endl;
}

Measured memory_bytes: 1312
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)

int main() {
	ll X, Y, Z;
	cin >> X >> Y >> Z;
	cout << Z << " " << X << " " << Y << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N, A, B;
    cin >> N >> A >> B;
    vector<int> cnt(3);
    for (int i = 0; i < N; i++) {
        int p; cin >> p;
        if (p <= A) cnt[0]++;
        else if (p <= B) cnt[1]++;
        else cnt[2]++;
    }
    cout << *min_element(cnt.begin(), cnt.end()) << '\n';
}


Measured memory_bytes: 3612
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
typedef unsigned long long ull;
#define rep(i,a) for(int i=0;i<a;i++)
#define loop(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const double eps = 1e-10;
const double pi = acos(-1);
const double inf = (int)1e8;

int main(void){
  int N,T,E;
  cin>>N>>T>>E;
  vector<int> in(N);
  rep(i,N)cin>>in[i];
  bool find = false;
  rep(i,N){
    int timer = 0;
    while(timer < T){
      timer+=in[i];
    }
    if(timer<=T+E){
      find = true;
      cout<<++i<<endl;
      break;
    }
  }						
  if(!find)cout<<-1<<endl;
}

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

int m, c, x, ii = 0;

void mcxiDisassembly(string& mcxi){
	int sum = 0;
	int number = 0;
	for (int i = 0; i <= mcxi.length(); i++){
		if (mcxi[i] != 'm' && mcxi[i] != 'c' && mcxi[i] != 'x' && mcxi[i] != 'i'){
			number = (int)(mcxi[i] - '0');
		}
		else{
			switch (mcxi[i]){
			case 'm':	if (number == 0){
							m += 1;
						}
						else{
							m += number;
						}
						break;

			case 'c':	if (number == 0){
							c += 1;
						}
						else{
							c += number;
						}
						break;

			case 'x':	if (number == 0){
							x += 1;
						}
						else{
							x += number;
						}
						break;

			case 'i':	if (number == 0){
							ii += 1;
						}
						else{
							ii += number;
						}
						break;
			}
			number = 0;
		}
	}
}

void show(){
	if (m != 0){
		if (m == 1){
			cout << 'm';
		}
		else{
			cout << m << 'm';
		}
	}
	if (c != 0){
		if (c == 1){
			cout << 'c';
		}
		else{
			cout << c << 'c';
		}
	}
	if (x != 0){
		if (x == 1){
			cout << 'x';
		}
		else{
			cout << x << 'x';
		}
	}
	if (ii != 0){
		if (ii == 1){
			cout << 'i';
		}
		else{
			cout << ii << 'i';
		}
	}
	cout << endl;
}

int main(){
	string mcxi1,mcxi2;
	int n;

	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> mcxi1 >> mcxi2;
		//????§£
		mcxiDisassembly(mcxi1);
		mcxiDisassembly(mcxi2);
		if (ii >= 10){
			x += ii / 10;
			ii -= (ii/10) * 10;
		}
		if (x >= 10){
			c += x / 10;
			x -= (x / 10) * 10;
		}
		if (c >= 10){
			m += c / 10;
			c -= (c / 10) * 10;
		}
		//??¨???
		show();
		m = c = x = ii = 0;
	}
	return 0;
}

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

using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<pair<long long, long long> > stores(n);
  for(int i=0; i<n; ++i){
   long long a, b;
   cin >> a >> b;
   stores[i] = {a, b};
  } 
  sort(stores.begin(), stores.end(),[](const pair<long long, long long> &a, const pair<long long, long long> &b){
    if(a.first == b.first)
      return a.second > b.second;
    return a.first < b.first;
  }
  );
  long long res = 0;
  int k = 0;
  while(m > 0){
   long long remove = min((long long)m, stores[k].second);
   m -= remove;
   res += stores[k].first*remove;
   ++k;
  }
  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 1792
t = int(input())
a = list()

for _ in range(t):
    
    c,d = map(int,input().split())
    a.append((c,d))
    
a.reverse()

g = 0

for i in range(t):
    
    f = (a[i][0]+g)%a[i][1]
    if(f!=0):
        f = a[i][1]-f
    g += f

print (g)

Measured memory_bytes: 55384
#include<bits/stdc++.h>
#define ll long long

using namespace std;
vector<string> w;
void solve(){
    int N;
    string str;
    char l_term;
    char f_term;
    cin>>N;
    cin>>str;
    w.push_back(str);
    l_term=str[str.size()-1];
    int num;    
    for(int i=1;i<N;i++){
        cin>>str;
        f_term=str[0];
        if(f_term!=l_term){
            cout<<"No"<<endl;
            return;
        }
        l_term=str[str.size()-1];
        
        //cout<<f_term<<endl;
        //cout<<l_term<<endl;
        w.push_back(str);    
    }
    sort(w.begin(),w.end());
    if(w.end()!=unique(w.begin(),w.end())){
        cout<<"No"<<endl;
        return;
    }
    cout<<"Yes"<<endl;
}

int main(){

    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define lb lower_bound
#define ub upper_bound
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
const ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}



signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll n,ans=0;cin>>n;
  rep(i,1,n+1){
    ll a=i%10,b=i,cnt=0,tmp;
    if(a==0)continue;

    while(b/10){
      b/=10;
      cnt++;
    }
    
    if(a==b){
      if(a<=n)ans++;
    }

    rep(j,1,INF){
      if(n<b+a*mpow(10,j))break;
      //cerr<<n<<" "<<i<<" "<<b+a*mpow(10,j)<<ENDL;

      tmp=b+a*mpow(10ll,j);
      if(tmp+10*(mpow(10ll,j-1)-1)<=n)ans+=mpow(10ll,j-1);
      else ans+=(n-b)/10 -a*mpow(10ll,j-1) +1;
    }
    

    //cerr<<i<<" "<<ans<<ENDL;
  }
  cout<<ans<<ENDL;
}
//( ・ __ ・ ) KEEP BEING ORGANIZED
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 256
def main():
    N = int(input())
    S = input()
    tree = SegmentTree(S, f=lambda x,y:x|y, converter=lambda c: 1 << (ord(c)-ord('a')))
    Q = int(input())
    update = tree.update
    query = tree.query
    for _ in range(Q):
        t, a, b = input().split()
        if t == '1': update(int(a)-1, b)
        else: print(bin(query(int(a)-1, int(b))).count('1'))    

class SegmentTree:
    def __init__(self, initial_values, f=max, zero_factory=int, converter=lambda x:x):
        self.__f, self.__z, self.__c = f, zero_factory, converter
        self.__n = 1 << ((len(initial_values) - 1).bit_length())
        self.__dat = [zero_factory() for _ in range(2 * self.__n)]
        zi = self.__get_leaf(0)
        for i, v in enumerate(initial_values): self.__dat[zi + i] = converter(v)
        for i in range(zi-1, -1, -1): self.__dat[i] = f(*self.__get_children(i))

    def update(self, index, value):
        i, v = self.__get_leaf(index), self.__c(value)
        if self.__dat[i] == v: return
        self.__dat[i] = v
        while i:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__z()
        if to_exclusive <= from_inclusive: return ans
        l, r = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        while r - l > 1:
            if self.__is_right(l): ans = self.__f(ans, self.__dat[l])
            if self.__is_left(r): ans, r = self.__f(ans, self.__dat[r]), r-1
            l, r = l//2, self.__get_parent(r)
        ans = self.__f(ans, self.__dat[l])
        if l != r: ans = self.__f(ans, self.__dat[r])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

if __name__ == '__main__':
    main()


Measured memory_bytes: 116300
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;

int main(){
  double r;
  double s,p;

  cin>>r;
  s=pow(r,2)*M_PI;
  p=2*r*M_PI;
  printf("%7f %7f\n",s,p);
  return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const int N=100000;
ll s[100000]={};

int main()
{
    int a;
    cin >>a;

    for(int i=1; i<N; ++i) s[i] = s[i-1]+i;

    int idx = 0;
    while(idx<N && s[idx]<a) ++idx;

    a = s[idx]-a;

    cout << string(idx-a,')')+"("+string(a,')')+string(idx-1,'(') << endl;
    return 0;
}

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

#define int long long
#define rep(i, n) for (int i = 0; i < (int) (n); i++)
#define reps(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), (x).end()))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N;
int A[110000];
signed main() {
    cin >> N;
    rep(i, N) { cin >> A[i]; }
    int s = accumulate(A, A + N, 0LL);
    int k = N * (N + 1) / 2;
    if (s % k != 0) { fin("NO"); }
    int a = s / k, b = 0;
    rep(i, N) {
        int diff = A[(i + 1) % N] - A[i];
        if (diff > a) { fin("NO"); }
        if ((a - diff) % N != 0) { fin("NO"); }
        b += (a - diff) / N;
    }
    if (a == b) { cout << "YES" << endl; }
    else { cout << "NO" << endl; }
}


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

int main(void){
	int N;
	cin>>N;
	if(N%2==0){
		bool dame=false;
		int m=N/2;
		vector<int> v(m,0);
		for(int i=0; i<N; i++){
			int tmp=0;
			cin >> tmp;
			v[tmp/2]++;
			if(v[tmp/2]>2){
				dame=true;
			}
			if(dame) break;
		}
		if(dame){
			cout<<0<<endl;
		} else {
			int k=1;
			for(int i=0; i<m; i++){
				k=(k*2)%(1000000000+7);
			}
			cout<<k<<endl;
		}
	} else {
		bool dame=false;
		int m=N/2;
		vector<int> v(m,0);
		int num_z=0;
		for(int i=0; i<N; i++){
			int tmp=0;
			cin >> tmp;
			if(tmp==0){
				num_z++;
				if(num_z>1){
					dame=true;
				}
			//cout<<num_z+100<<endl;
			} else {
				v[tmp/2-1]++;
				if(v[tmp/2-1]>2){
					dame=true;
				}
			//cout<<tmp/2-1<<v[tmp/2-1]<<endl;
			}
			if(dame) break;
		}
		if(dame){
			cout<<0<<endl;
			//cout<<"だめ"<<endl;
		} else {
			int k=1;
			for(int i=0; i<m; i++){
				k=(k*2)%(1000000000+7);
			}
			//cout<<"大丈夫"<<endl;
			cout<<k<<endl;
		}
	}
	return 0;
}

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

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(1e3) + 17;

struct item {
    int w, s;
    ll val;
    item() = default;
    item(int w, int s, ll val) : w(w), s(s), val(val) { }
};

bool operator <(item a, item b) { return mp(a.s + a.w, -a.val) < mp(b.s + b.w, -b.val); }

int n;
item a[MAXN];
ll dp[MAXN][int(2e4) + 10];

bool read() {
    if (!(cin >> n))
        return false;

    forn (i, n)
        cin >> a[i + 1].w >> a[i + 1].s >> a[i + 1].val;

    return true;
}

void solve() {
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= 2e4; ++w)
            dp[i][w] = dp[i - 1][w];

        for (int w = 0; w <= a[i].s; ++w)
            dp[i][min(int(2e4) + 1, w + a[i].w)] = max(dp[i][min(int(2e4) + 1, w + a[i].w)], dp[i - 1][w] + a[i].val);
    }

    ll ans = 0;

    for (int w = 0; w <= 2e4; ++w)
        ans = max(ans, dp[n][w]);

    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
#ifdef SEREZHKA
    freopen("file.in", "r", stdin);
#endif
    
    while (read())
        solve();
    
    return 0;
}



Measured memory_bytes: 157824
<?php
$s = $a[0] = range(1, 9);
$keta = 0;
while(count($s) < 100000) {
    foreach ($a[$keta] as $v) {
        $w = str_split(strval($v));
        $l = $w[count($w) - 1];
        if ($l !== '0') {
            $tmp = $w;
            array_push($tmp, strval($l - 1));
            $a[$keta + 1][] = intval(implode('', $tmp));
        }
        $tmp = $w;
        array_push($tmp, strval($l));
        $a[$keta + 1][] = intval(implode('', $tmp));
        if ($l !== '9') {
            $tmp = $w;
            array_push($tmp, strval($l + 1));
            $a[$keta + 1][] = intval(implode('', $tmp));
        }
    }
    $s = array_merge($s, $a[$keta + 1]);
    $keta++;
}
fscanf(STDIN, "%d", $N);
$NN = intval($N);
printf("%d", $s[$N - 1]);


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

int abs(int a){
	return (a>0)?a:-a;
}

int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(abs(a-c)>d){
		if(abs(a-b)>d or abs(b-c)>d)cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}else cout<<"Yes"<<endl;
	return 0;
}

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

int main() {
  int N, M;
  int p[100005];
  int i, j;
  string S[100005];
  bool flag[100005];
  int sum = 0;
  int cnt = 0;
  cin >> N >> M;
  for (i = 1; i <= N; i++)
    flag[i] = false;
  for (i = 0; i < M; i++) {
    cin >> p[i];
    cin >> S[i];
    if (S[i][0] == 'A' && S[i][1] == 'C')
      flag[p[i]] = true;
  }
  for (i = 1; i <= N; i++)
    if (flag[i])
      cnt++;
  for (i = 0; i < M; i++) {
    if (S[i][0] == 'W' && S[i][1] == 'A' && flag[p[i]] == 1)
      sum++;
    else if (S[i][0] == 'A' && S[i][1] == 'C')
      flag[p[i]] = false;
  }
  cout << cnt << ' ' << sum << endl;
}


Measured memory_bytes: 6144
N = int(input())
old_dl = [list(map(int,input().split())) for _ in range(N)]
dl = []
for k in old_dl:
    if k[2] != 0:
        dl.append(k)
if len(dl) == 1:
    print(*dl[0])
else:
    for x in range(101):
        for y in range(101):
            ndl = [l[2]+abs(l[0]-x)+abs(l[1]-y) for l in dl]
            if max(ndl) == min(ndl):
                #print(ndl)
                print(x,y,max(ndl))
                exit(0)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,n)  for(ll i=0;i<n;i++)
#define fb(i,n) for(ll i=n-1;i>=0;i--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef pair<int,int> pii;
int main()
{
	IOS;
	//int t; cin>>t;
	int t=1;
	while(t)
	{
		ll n; cin>>n;
		string s="";
		while(n)
		{
			int w=n%26;
			char c = (int)w+96;
			if(w==0)
			{
				c='z';
				n=n/26;
				n--;
			}
			else n=n/26;
			s=c+s;
		}
		cout<<s;
		t--;
	}
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
  using namespace std;
  long long MOD=1000000007;
  #define IOS() ios_base::sync_with_stdio(0); cin.tie(0);
  typedef long long ll;
  #define pb push_back
  typedef pair<ll,ll> pi;
  double dp[305][305][305];

double solve(int x, int y,int z, int n)
{
  if(x==0 && y==0 && z==0)
    return 0;
  if(x<0 || y<0 || z<0)
    return 0;

  if(dp[x][y][z]>0)
    return dp[x][y][z];

  double exp=n+ x*solve(x-1,y,z,n) + y*solve(x+1,y-1,z,n) + z*solve(x,y+1,z-1,n);
  return dp[x][y][z]=exp/(x+y+z);


}


int main()
{
  IOS();
  memset(dp,-1,sizeof dp);
  int ones=0;
  int two=0;
  int three=0;
  int temp;
  int n;
  cin>>n;
  for (int i = 0; i < n; ++i)
  {
      cin>>temp;
      if(temp==1)
        ones++;
      else if(temp==2)
        two++;
      else
        three++;


  }


  cout<<fixed<<setprecision(12)<<solve(ones,two,three,n)<<endl;

  return 0;
}

Measured memory_bytes: 225452
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>>vvi;

int main(){
  int s;
  cin>>s;
  set<int>SET;
  SET.insert(s);
  for(int i=2;i<=1000000;i++){
    if(s%2==0)s=s/2;
    else s=3*s+1;
    if(SET.count(s)){
      cout<<i<<endl;
      return 0;
    }
    else SET.insert(s);
  }
}

Measured memory_bytes: 256