akhauriyash/Code-Regression huggingface dataset:
import cmath
import sys

INF=10**18
MOD=998244353
MAX=10**5+7

def main():
    S=int(input())

    l=1
    r=10**9

    while l+1<r:
        mid=(l+r)//2
        if mid*mid<=S:
            l=mid
        else:
            r=mid

    ans=[0, 0, r, 1, r*r-S, r]
    print(*ans)

if __name__=='__main__':
    main()


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

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

    int c = a + k - 1, d = b - k + 1;

    if (c >= d || c >= b || d <= a)
        for (int i = a; i <= b; i++)
            cout << i << endl;
    else {
        for (int i = a; i <= c; i++)
            cout << i << endl;
        for (int i = d; i <= b; i++)
            cout << i << endl;
    }
}

Measured memory_bytes: 3524
n = gets.chomp.to_i
  
ans = []

n.times do |i|
  ans_count = gets.chomp.to_i
  ans[i] = []
  ans_count.times do |j|
    x, y = gets.chomp.split().map(&:to_i)
    ans[i][j] = [x-1, y == 1]
  end
end

result = 0

catch :finish do
  [true, false].repeated_permutation(n) do |comb|
    catch :next_comb do
      n.times do |i|
        next unless comb[i]
        #i番目の人が正直なとき矛盾するかどうか
        ans[i].each do |an|
          #an[0]番目の人がan[1]だと言っている
          throw :next_comb if comb[an[0]] != an[1] #矛盾していたら終了
        end
      end
      result = comb.count {|c| c }
      throw :finish
    end
  end
end

puts result

Measured memory_bytes: 2044
#include<iostream>
#include<string>
#include<math.h>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>

#define ll long long
#define vl vector<ll>
#define vvl vector< vector<ll> >
#define vb vector<bool>
#define vbb vector< vector<bool> >
#define vs vector<string>
#define vc vector<char>
#define vvc vector< vector<char> >

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

using namespace std;

int main(){
	ll a, b, c, x; cin >> a >> b >> c >> x;
	ll ans = 0;
	for (ll i = 0; i <= a; ++i){
		for (ll j = 0; j <= b; ++j){
			for (ll k = 0; k <= c; ++k){
				if (x == 500 * i + 100 * j + 50 * k) ans++;
			}
		}
	}cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
S=int(input())
A=[]
i=0
for x in range(0,4):
    A.append(S%10)
    S=S//10
if A[0]==A[1]:
    i=1
if A[1]==A[2]:
    i=1
if A[2]==A[3]:
    i=1
if i==0:
    print("Good")
else:
    print("Bad")


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;

struct TWO{
    long long int a,b;
};

bool cmp(TWO x,TWO y){
    if(x.a!=y.a){
        return x.a<y.a;
    }else{
        return x.b<y.b;
    }
}

int f[51][51];
int h, w;

void dfs(int y, int x) {
    if (f[y][x] == 0) return;
    f[y][x] = 0;
    int dx[3] = {-1, 0, 1};
    int dy[3] = {-1, 0, 1};
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int nx = x + dx[i];
            int ny = y + dy[j];
            if (nx < 0 || nx == w || ny < 0 || ny == h) continue;
            if (f[ny][nx] == 1) {
                dfs(ny, nx);
            }
        }
    }
}

int main() {
    const long long int mod = 1000000007,INF=50000000000000;
    typedef pair<long long int,long long int>P;
	map<long long int, long long int>mp;
    priority_queue<P,vector<P>,greater<P> >mazuisushi;
    
    priority_queue<P>umaisushi;
	cout << fixed << setprecision(10);
    string str;
    long long int y,m,d;

    while(1){
        cin >> w >> h;
        if (w == 0) return 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> f[i][j];
            }
        }
        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (f[i][j] == 0) continue;
                dfs(i, j);
                cnt++; 
            }
        }
        cout << cnt << endl;
    }
} 



Measured memory_bytes: 3352
#include<iostream>
using namespace std;
#define MAX_N 400000
bool prime[MAX_N];
int num[MAX_N];
int main(){
	for(int i=0;i<MAX_N;i++){
		prime[i]=1;
	}
	prime[0]=0;
	prime[1]=0;
	for(int i=2;i<MAX_N;i++){
		if(prime[i]){
			for(int j=2;j*i<MAX_N;j++){
				prime[i*j]=0;
			}
		}
	}
	for(int i=1;i<MAX_N;i++){
		if(prime[i]){
			num[i]=num[i-1]+1;
		}else{
			num[i]=num[i-1];
		}
	}
	int a;
	while(cin>>a&& a!=0){
		cout<<num[a*2]-num[a]<<endl;
	}

}

Measured memory_bytes: 3112
#include <cstdio>

const int MAX_H = 103;
const int MAX_W = 103;
const char X = 'X';

char dp[][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

void readline(char line[]) {
    int ch, i = 0;
    while ((ch = getchar()) && ch != EOF && ch != '\n') {
        line[i++] = ch;
    }
    line[i] = '\0';
}

char field[MAX_H][MAX_W];
int H, W;

void dfs(int h, int w) {
    char CH = field[h][w];
    field[h][w] = X;

    for (int i = 0; i < 4; ++i)
    {
        int dh = dp[i][0], dw = dp[i][1];
        char c = field[h+dh][w+dw];
        if (c != X && c == CH)
            dfs(h+dh, w+dw);
    }
}

int main(int argc, char const *argv[])
{
    scanf("%d %d\n", &H, &W);
    while (H && W) {
        for (int i = 0; i < W+2; ++i)
        {
            field[0][i] = field[H+1][i] = X;
        }

        for (int i = 1; i < H+1; ++i)
        {
            readline(&field[i][1]);
            field[i][0] = field[i][W+1] = X;
        }

        int count = 0;
        for (int i = 0; i < H+2; ++i)
        {
            for (int j = 0; j < W+2; ++j)
            {
                if (field[i][j] != X) {
                    count++;
                    dfs(i, j);
                }
            }
        }

        printf("%d\n", count);
        scanf("%d %d\n", &H, &W);
    }

    return 0;
}

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

int main()
{
  int A, B, M, ans = 0;
  cin >> A >> B >> M;
  vector<int> reizoko, renji;
  vector<int> xm, ym, cm;
  int amin = 1000000;
  int bmin = 1000000;
  rep(i, A)
  {
    int a;
    cin >> a;
    if (amin > a)
      amin = a;
    reizoko.push_back(a);
  }
  rep(i, B)
  {
    int b;
    cin >> b;
    if (bmin > b)
      bmin = b;
    renji.push_back(b);
  }
  int waribiki = 1000000;
  rep(i, M)
  {
    int x, y, c;
    cin >> x >> y >> c;
    xm.push_back(x);
    ym.push_back(y);
    cm.push_back(c);
    if (waribiki > reizoko[x - 1] + renji[y - 1] - c)
      waribiki = reizoko[x - 1] + renji[y - 1] - c;
  }

  if (amin + bmin > waribiki)
  {
    cout << waribiki << endl;
  }
  else
  {
    cout << amin + bmin << endl;
  }
  return 0;
}

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

class Baseball{
private:
	int point;
	int out_count;
	int runner;
public:
	Baseball();
	void singleHit();
	void homerun();
	void out();
	void new_inning();
	int get_out_count();
	int get_point();
	~Baseball() = default;
};

Baseball::Baseball(){
	new_inning();
}

void Baseball::singleHit(){
	if(runner < 3){
		++runner;
	}
	else if(runner == 3){
		++point;
	}
}

void Baseball::homerun(){
	point += runner + 1;
	runner = 0;

}

void Baseball::out(){
	++out_count;
}

void Baseball::new_inning(){
	point = 0;
	out_count = 0;
	runner = 0;
}

int Baseball::get_out_count(){
	return out_count;
}

int Baseball::get_point(){
	return point;
}

int main(){
	int num;
	std::cin >> num; //data set number
	Baseball baseball;
	std::string event;
	
	for(int i=0; i<num; ++i){
		baseball.new_inning();
		
		while(baseball.get_out_count() < 3){
			std::cin >> event;
			
			if(event == "HIT"){
				baseball.singleHit();
			}
			else if(event == "HOMERUN"){
				baseball.homerun();
			}
			else if(event == "OUT"){
				baseball.out();
			}
		}
		//output
		std::cout << baseball.get_point() << std::endl;
	}

}

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

using namespace std;
using ll = long long;
using P = pair<int ,int>;
using  vi = vector<int>;
using vii = vector<P>;

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

#define INF 1LL << 62
#define MOD (int)1e9 + 7
#define rep(i,n) for(int i = 0;i<n;i++)
#define all(x) x.begin(),x.end()
#define pb push_back

int main() {

	int a, b;
	cin >> a >> b;

	int c = a + b;
	if (c >= 24)c -= 24;
	cout << c << endl;

	return 0;
}

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

using namespace std;
int s[4];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
	cin>>s[1]>>s[2]>>s[3];
	sort(s+1,s+4);
	int a= (s[1]*s[1])+(s[2]*s[2]);
	if(s[3]*s[3]==a)
	{cout<<"YES"<<endl;}
	else {
		cout<<"NO"<<endl;
	}
}
}



Measured memory_bytes: 3008
// B - Popular Vote
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	int N,M; cin>>N>>M;
	vector<int> A(N);
	int tot = 0;
	rep(i, N){
		cin>>A[i];
		tot += A[i];
		A[i] *= 4*M;
	}
	int c = 0;
	rep(i, N) if(tot <= A[i]) c++;
	puts(c >= M? "Yes":"No");
}

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

signed main(){
  int N,ans=0;
  cin>>N;
  string S;
  cin>>S;
  rep(i,N){
    if(S[i]=='A'&&S[i+1]=='B'&&S[i+2]=='C')ans+=1;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3600
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = sorted([[i+1, d] for i, d in enumerate(lr())], key=lambda x: x[1])[::-1]
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0] = 0
    for x in range(N):
        for y in range(N-x):
            i, d = A[x+y]
            dp[x+1, y] = max(dp[x, y]+d*(i-x-1), dp[x+1, y])
            dp[x, y+1] = max(dp[x, y]+d*(N-y-i), dp[x, y+1])
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i, N-i])
    print(ans)
resolve()

Measured memory_bytes: 415288
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

int N, R;
signed main(){
	cin >> N >> R;
	cout << R + max(10-N, 0)*100 << endl;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = 1
colors = {}
ends = {}
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    ng = {}
    global palette
    if parent > 0:
        ng[colors[parent]] = True
    for edge in edges[root]:
        if edge in colors:
            color = colors[edge]
        elif palette - len(ng) > 0:
            color = 1
            while color in ng:
                color += 1
            colors[edge] = color
        else:
            palette += 1
            color = palette
            colors[edge] = color

        ng[color] = True
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(palette)
for edge in range(1,N):
    print(colors[edge])


Measured memory_bytes: 99764
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll MOD = 1e9 + 7;
ll INF = 1e18;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<bool> dp(1e6, false);
    dp[0]=true;
    rep(i,1001){
        rep(j,100001){
            if(dp[j]){
                dp[j + 100] = true;
                dp[j + 101] = true;
                dp[j + 102] = true;
                dp[j + 103] = true;
                dp[j + 104] = true;
                dp[j + 105] = true;
            }
        }
    }
    ll n;
    cin >> n;
    if(dp[n]){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
int n;
int v[MAX+1],odd[MAX+1],even[MAX+1];
int cnte[MAX+1],cnto[MAX+1];
int e1,e2,o1,o2,maxe,maxo;

int main(){
	cin>>n;
	for (int i=1;i<=n;i++) cin>>v[i];
	for (int i=2;i<=n;i+=2) even[i/2]=v[i];
	for (int i=1;i<=n;i+=2) odd[(i+1)/2]=v[i];
	
	for (int i=1;i<=n/2;i++) cnte[even[i]]++;
	for (int i=1;i<=n/2;i++) cnto[odd[i]]++;
		
	for (int i=1;i<=MAX;i++)
		if (cnte[i]>=e1){e2=e1;e1=cnte[i];maxe=i;}
		else if (cnte[i]>=e2) e2=cnte[i];
	for (int i=1;i<=MAX;i++)
		if (cnto[i]>=o1){o2=o1;o1=cnto[i];maxo=i;}
		else if (cnto[i]>=o2) o2=cnto[i];
		
	//cout<<e1<<e2<<o1<<o2<<endl;
	//cout<<maxe<<" "<<maxo<<endl; 
	if (maxe!=maxo) cout<<n-(e1+o1)<<endl;
	else cout<<n-max(e1+o2,o1+e2)<<endl;
	return 0;
} 

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

using namespace std;

int k;
string s;
string t;

int Rec(int i = 0, int Last = -1)
{
    if(i == k)  return t <= s;

    int Res = 0;

    for(int j = Last + 1; j < s.size(); j++)
    {
        if(t[j] == '0')
        {
            for(int r = 1; r < 10; r++)
            {
                t[j] = r + '0';
                Res += Rec(i + 1, j);
                t[j] = '0';
            }
        }
    }

    return Res;
}

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

    t = string(s.size(), '0');

    cout << Rec() << endl;
}


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

class Program
{
    static void Main(string[] args)
    {
        var inputs = Console.ReadLine().Split(' ');
        var N = int.Parse(inputs[0]);
        var K = int.Parse(inputs[1]);

        if (K == 1)
        {
            Console.WriteLine(1);
            return;
        }

        double sum = 0;
        for (int n = 1; n <= N; n++)
        {
            double value = (double)(K - 1) / n;
            double log = Math.Log(value) / Math.Log(2.0);
            int k = (int)log + 1;
            double prob;
            if (K - 1 < n)
            {
                prob = 1.0 / N;
            }
            else
            {
                prob = 1.0 / N / Math.Pow(2, k);
            }
            sum += prob;
        }

        Console.WriteLine(sum);
    }


}



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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(a,b) for(int a=0;a<(b);++a)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
#define PI 3.14159265358979
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;
ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    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;
    }
}
ll 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;
}
ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool compare_by_a(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}

vector<pair<int,ll>> vec[100000];
ll cost[100000];
void dfs(int now,ll COST){
    cost[now]=COST;
    int next;
    REP(i,vec[now].size()){
        next=vec[now][i].first;
        if(cost[next]<0){
            dfs(next,COST+vec[now][i].second);
        }
    }
}
int counter(int x){
    if(!x)return 0;
    return counter(x>>1)+(x&1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N=in();
    double x;
    string s;
    double ans;ans=0;
    REP(i,N){
        cin>>x>>s;
        if(s=="BTC"){
            x*=380000;
        }
        ans+=x;
    }
    cout<<ans<<endl;
    return 0;
}


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

#define loop(n) for(int i = 0;i < (int)(n);++i)
#define rep(i,n) for(int i = 0;i < (int)(n);++i)
#define all(vec) (vec).begin(),(vec).end()
#define sort(vec) std::sort(all(vec))
#define rev(vec) std::reverse(all(vec))

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

void inputVector(){return;}
template<typename First,typename... Rest> void inputVector(std::vector<First> &first,Rest&... rest){
    int N = first.size();
    for(int i = 0;i < N;i++){
        std::cin >> first[i];
    }
    inputVector(rest...);
}

template<typename First,typename Second> void inputTwoVector(std::vector<First> &first,std::vector<Second>& second){
    int N = first.size();
    for(int i = 0;i < N;i++){
        std::cin >> first[i] >> second[i];
    }
}

double getDis(int x,int y,int x1,int y1){
    int xdis = std::abs(x - x1);
    xdis *= xdis;
    int ydis = std::abs(y - y1);
    ydis *= ydis;
    return (double)std::sqrt(xdis + ydis);
}

void calculate(){
    int K,S;
    int res = 0;
    input(K,S);
    rep(x,K + 1){
        rep(y,K + 1){
            int z = S - x - y;
            if(0 <= z and z <= K) res++;
        }
    }
    std::cout << res << '\n';
}

int main(int,char**){
    calculate();    
}




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

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

const long long MOD = 1000000007;

int main(){
  int n,l;
  cin >> n >> l;
  int ans = 0;
  int ma = 10000,a=0,t=0;
  rep(i,n){
    a=l+i;
    ans+=a;
    if(a<0){
      ma=min(ma,-a);
      t=1;
    }
    else{
      ma=min(ma,a);
      t=0;
    }
  }
  if(t) ans+=ma;
  else ans-=ma;
  cout << ans <<endl;
}


Measured memory_bytes: 256
from collections import deque


def shortest_cycle_path(graph, start):
    """重み無し有向グラフgraphに対して、startから出発してstartに帰るサイクルの最短経路を求める
    サイクルが存在しないときは空のリスト [] を返す
    例) start = 0 のときの最短サイクルが 0 -> 3 -> 1 -> 0 のとき、
        [0, 3, 1, 0] を返す
    """
    n = len(graph)
    dist = [-1] * n
    prev_pos = [-1] * n
    q = deque([start])
    dist[start] = 0
    while q:
        pos = q.pop()
        for next_pos in graph[pos]:
            if dist[next_pos] == -1:
                dist[next_pos] += dist[pos] + 1
                prev_pos[next_pos] = pos
                q.append(next_pos)

    # path := サイクル経路の頂点, path_len := サイクル長
    # サイクル長 = len(path) - 1 となることに注意
    path = []
    path_len = 10**9 + 7
    for goal in range(n):
        if start == goal or dist[goal] == -1:
            continue
        for next_pos in graph[goal]:
            # goalからstartへのパスが存在するとき(つまりサイクルが存在するとき)
            if next_pos == start:
                tmp_path = []
                pos = goal
                while True:
                    tmp_path.append(pos)
                    if pos == start:
                        break
                    pos = prev_pos[pos]
                if len(tmp_path) < path_len:
                    path_len = len(tmp_path)
                    path = [start] + tmp_path[0:]
    path = path[::-1]
    return path


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)

len_ans = 10**9 + 7
ans = []
for i in range(n):
    tmp = shortest_cycle_path(graph, i)
    if len(tmp) != 0 and len(tmp) < len_ans:
        len_ans = len(tmp)
        ans = tmp
if ans:
    print(len(ans) - 1)
    for i in range(len(ans) - 1):
        print(ans[i] + 1)
else:
    print(-1)


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

using namespace std;

typedef long long ll;
typedef long double ld;

int t[3];

int turn(char x){
    if(x == 'a') return 0;
    if(x == 'b') return 1;
    return 2;
}

string s[3];
int k;

int main(){
    ios_base::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;

    cin >> s[0] >> s[1] >> s[2];
    while(1){
        if(t[k] >= s[k].size()){
            if(k == 0) cout << "A";
            else if(k == 1) cout << "B";
            else cout << "C";
            return 0;
        }
        int r = k;
        k = turn(s[k][t[k]]);
        t[r]++;
    }
    return 0;
}


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

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
const int B = 12345;

int K, L;
int Lnum;
int pB[100001];
int A[100001];
int TA[100001];
string S;

bool g(int pos, string &T) {
  int lo = -1, hi = T.length();
  while (hi - lo > 1) {
    int mid = (lo + hi) / 2;
    // [0, mid]
    int a = (A[pos+mid]+MOD-(pos>0?A[pos-1]:0)) % MOD;
    if (a == (1LL*pB[pos]*TA[mid])%MOD) lo = mid;
    else hi = mid;
  }
  int lcp = lo+1;
  if (lcp == T.length()) return true;
  return S[pos+lcp] <= T[lcp];
}

bool f(string &T) {
  int pos = 0;
  int cl = 0, cr = 0;
  rep(_, K) {
    assert(pos < S.length());
    if (cl < Lnum && g(pos, T)) {
      pos += L;
      cl++;
    }
    else {
      if (cr >= K-Lnum) return false;
      pos += L-1;
      cr++;
    }
  }
  assert(pos == S.length() && cl == Lnum && cl+cr == K);
  return true;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  pB[0] = 1;
  for (int i=1; i<=100000; i++) pB[i] = (1LL*B*pB[i-1]) % MOD;
  cin >> K >> S;
  if (K == 0) {
    cout << S << "\n";
    return 0;
  }
  rep(i, S.length()) A[i] = ((i>0?A[i-1]:0)+1LL*S[i]*pB[i]) % MOD;
  K++;
  L = (S.length()+K-1)/K;
  Lnum = S.length()%K;
  if (S.length()%K==0) Lnum = K;
  string T;
  rep(i, L) {
    int dig = 9;
    for (int c=1; c<=8; c++) {
      string ct(T);
      ct += (char)('0'+c);
      TA[i] = ((i>0?TA[i-1]:0) + 1LL*pB[i]*ct.back()) % MOD;
      if (f(ct)) {
        dig = c;
        break;
      }
    }
    T += (char)('0'+dig);
    TA[i] = ((i>0?TA[i-1]:0) + 1LL*pB[i]*T.back()) % MOD;
  }
  cout << T << "\n";
  return 0;
}


Measured memory_bytes: 1616
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n,y;

int main(){
    scanf("%d%d",&n,&y);
    for(int i=0;i<=n&&10000*i<=y;i++)//钱总数大于Y，停止
        for(int j=0;i+j<=n&&10000*i+5000*j<=y;j++)//钞票数大于N，停止 或 钱总数大于Y，停止
            if((y-10000*i-5000*j)%1000==0&&(y-10000*i-5000*j)/1000==n-i-j){
            //N-I-J的就是1000的数量，如果可以就找到解啦
                printf("%d %d %d\n",i,j,(y-10000*i-5000*j)/1000);
                return 0;
            }
    //如果一组解也没有，那我也没办法。。。
    printf("-1 -1 -1\n");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int N,a,ans;
long long f[100000001];
int main(void){
    cin>>N;
    for(int x=1;x<=100;x++)for(int y=1;y<=100;y++)for(int z=1;z<=100;z++)f[x*x+y*y+z*z+x*y+y*z+z*x]++;
    for(int i=1;i<=N;i++)cout<<f[i]<<endl;
    return 0;
}

Measured memory_bytes: 4088
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

struct BIT{
  int n;
  vector<ll> data;
  BIT(int n) : data(n + 1, 0), n(n){}
  ll sum(int i){
    ll s = 0;
    while(i > 0){
      s += data[i];
      i -= i & -i;
    }
    return s;
  }
  void add(int i, ll x){
    while(i <= n){
      data[i] += x;
      i += i & -i;
    }
  }
};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin>>n;
  int A[n];
  FOR(i,0,n) cin>>A[i];
  int B[n];
  FOR(i,0,n) B[i]=A[i];
  sort(B, B + n);
  map<ll, int> M;
  FOR(i,0,n){
    M[B[i]] = i + 1;
  }
  ll ans = 0;
  BIT bit(202020);
  FOR(i,0,n){
    ans += bit.sum(200020) - bit.sum(M[A[i]]);
    bit.add(M[A[i]], 1);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 18424
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))

ans=0
for i in range(N-1):
    x=A[i]
    ans+=x//2
    if x%2==1 and A[i+1]>=1:
        ans+=1
        A[i+1]-=1

ans+=A[N-1]//2
print(ans)


Measured memory_bytes: 80576
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    ll H, W;
    cin >> H >> W;
    ll ans = 0;
    if(H ==1 or W == 1)
    {
        ans = 1;
    }
    else if (H % 2 == 0)
    {
        ans = H / 2 * W;
    }
    else if (W % 2 == 0)
    {
        ans = H * W / 2;
    }
    else
    {
        ans = ((H + 1) / 2) * ((W + 1) / 2) + (H / 2) * (W / 2);
    }

    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <functional>

using namespace std;

typedef long long int ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
	string s;
	while (true)
	{
		cin >> s;
		if (s == "0")
		{
			break;
		}
		int sum = 0;
		REP(i, s.length())
		{
			sum += (int)(s[i] - '0');
		}
		cout << sum << endl;
	}
	return 0;
}


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

int main() {
  long long X, sum=100, count=0;
  cin >> X;
  
  while(X>sum) {
  long long intr = sum * 1 / 100;
  sum += intr;
  count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const double pi=3.1415926535;

signed main()
{
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    ll cnt=0;
    if(k<=a+b){
    	if(k<a)cnt=k;
    	else cnt=a;
	}
	else cnt=a-(k-a-b);
	cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(a,n) rep(i,0,n){ cout<<(i ? " ":"")<<a[i]; }cout<<endl;
int main(){
	int N;cin>>N;
	int a;map<int,int> count;
	rep(i,0,N){
		cin>>a;
		count[a]++;
	}int b=0,c=0;
	for(pair<int,int> u:count){
        b++;
		c+=u.second-1;
	}cout<<b-(c%2 ? 1 : 0)<<endl;
}

Measured memory_bytes: 4992
N = int(input())
S = input()

Ecnt = S.count('E')
Wcnt = S.count('W')

E = [0] * N
W = [0] * N

if S[0]=='E':
    E[0] = 1
else:
    W[0] = 1

for i in range(1, N):
    if S[i]=='E':
        E[i] = E[i-1] + 1
        W[i] = W[i-1]
    else:
        W[i] = W[i-1] + 1
        E[i] = E[i-1]
        
E = [0] + E
W = [0] + W
# print('E', E, 'W', W)

score=[]
for i in range(N):
        score.append(W[N]-W[i+1] + E[i]-E[0])
print(N-max(score)-1)

Measured memory_bytes: 30932
///                ..:: In The Name Of God ::..
#include <bits/stdc++.h>

#define REP(i, N) for (int i = 0,N; i <= N; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define endl    '\n' 
#define INF 2e9
#define int ll
#define vi          vector<int>
#define de          deque<int>
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()//全範囲指定を簡略化

typedef long long ll;

using namespace std;

//配列の要素数は　sizeof(ar)/sizeof(ar[0]) で求める

signed main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int N, X;

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

    int flag = 1;
    ll point = 0;
    for (int i = 0;i < N; i++){
        point += v[i];
        if (point <= X){
            flag += 1; 
        }
    }

    cout << flag << endl;
}


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

int main(){
        int n;
        int a[110];
        bool color[8]={false};
        int freecolor=0,ans=0;
        cin>>n;
        for(int i=0; i<n; ++i) cin>>a[i];

        for(int i=0; i<n; ++i){
                int num=a[i]/400;
                if(num>=8) ++freecolor;
                else if(!color[num]){
                        color[num]=true;
                        ++ans;
                }
        }

        if(ans==0) {
                ans=1;
                --freecolor;
        }

        cout<<ans<<" "<<ans+freecolor<<endl;
	return 0;
}


Measured memory_bytes: 384
using System;
using static System.Console;
using static System.Math;

namespace Main
{
    class Program
    {
        static int INF = 10000;
        static void Main(string[] args)
        {
            string[] tmp = ReadLine().Split(' ');
            int H = int.Parse(tmp[0]);
            int W = int.Parse(tmp[1]);

            char[,] s = new char[H + 1, W + 1];
            int[,] d = new int[H + 1, W + 1];

            for (int j = 0; j <= W; j++)
            {
                d[0, j] = INF;
            }

            for (int i = 1; i <= H; i++)
            {
                d[i, 0] = INF;
                char[] line = ReadLine().ToCharArray();
                for (int j = 1; j <= W; j++)
                {
                    s[i, j] = line[j - 1];
                }
            }

            s[0, 1] = '.';
            d[0, 1] = 0;

            for (int i = 1; i <= H; i++)
            {
                for (int j = 1; j <= W; j++)
                {
                    int l;
                    int u;

                    if (s[i, j] == '.')
                    {
                        d[i, j] = Min(d[i, j - 1], d[i - 1, j]);
                    }
                    else
                    {
                        if (s[i, j - 1] == '.')
                        {
                            l = d[i, j - 1] + 1;
                        }
                        else
                        {
                            l = d[i, j - 1];
                        }

                        if (s[i - 1, j] == '.')
                        {
                            u = d[i - 1, j] + 1;
                        }
                        else
                        {
                            u = d[i - 1, j];
                        }

                        d[i, j] = Min(l, u);
                    }
                }
            }

            Write(d[H, W]);
        }
    }
}

Measured memory_bytes: 11152
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include<random>
#include<math.h>
#include<limits.h>
#include<iterator>
#include<queue>
#define rep(i,a) for(int i=0;i<a;i++)
#define nrep(i,a,b) for(int i=a;i<b;i++)
#define mrep(i,a) for(int i=a;i>=0;i--)
#define ll long long
#define vl vector<ll> 
#define vvl vector<vector<ll> > 
#define vb vector<bool> 
#define vvb vector<vector<bool> > 
#define INF 11234567890123456789
using namespace std;
 
ll lcm(ll a, ll b){
	ll root_a = a;
	ll root_b = b;
	ll tmp;
	/* 自然数 a > b を確認・入替 */
	if (a<b){
		tmp = a;
		a = b;
		b = tmp;
	}
 
	/* ユークリッドの互除法 */
	ll r = a % b;
	while (r != 0){
		a = b;
		b = r;
		r = a % b;
	}
	if (!(root_a % b)) return (root_a / b)*root_b;
	else return (root_b / b)*root_a;
}
 
int main(){
	ll n; cin >> n;
	vl t(n);
	ll mini = INF;
	ll ans = 1;
	rep(i, n){
		cin >> t[i];
		if (!i) ans = t[i];
		ans = lcm(ans, t[i]);
		mini = min(mini, t[i]);
	}ll maxi = 0;
	cout << ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << "\n"; }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}


#line 2 "tmp.cpp"

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

  ll i, o, t, j, l, s, z;
  cin >> i >> o >> t >> j >> l >> s >> z;
  ll ans = o + 2 * (i / 2) + 2 * (j / 2) + 2 * (l / 2);
  if (i >= 1 && j >= 1 && l >= 1)
    chmax(ans, o + 2 * ((i - 1) / 2) + 2 * ((j - 1) / 2) + 2 * ((l - 1) / 2) + 3);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
h = list(map(int, input().split()))
ans = 0
INF = float("inf")
while True:
  # 左端から０以外の値（問題のｌ）を探す
  # 毎度左端から探すので、リスト中の０部分列が左から伸びてきても問題ない
  left = -1
  for i in range(N):
    if h[i] != 0:
      left = i
      break
  if left == -1:
    break #すべてが０になったので終了
  
  # leftの位置から０の手前まで（問題のr）を探す
  # index()は見つからない場合エラーが戻ってくるのでだめ
  right = -1
  for i in range(left, N):
    if h[i] == 0:
      right = i - 1
      break
      
    if i == N - 1:
      right = N - 1

  min_length = min(h[left:right+1])
  # 部分配列から一番小さい値を取り去る
  for i in range(left, right+1):
    h[i] -= min_length
  
  ans += min_length
  
  
  
print(ans)
  

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

int main()
{
  int temp,temp2;
  int input_num;
  cin >> input_num;
  for(int i = 0; i < input_num;i++)
  {
      temp = i + 1;
      if((temp % 3) == 0 || ((temp%10)%10) == 3)
      {
          cout << " " << temp;
      }else
      {
        temp2 = temp;
        while(temp > 1)
        {
          temp /= 10;
          if(temp % 10 == 3)
          {
            cout << " " << temp2;
            break;
          }
        }

      }

  }
  cout << "\n";
  return 0;
}




Measured memory_bytes: 3096
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	int n,a,b;
	string s;
	int m=0,l=0;
	cin>>n>>a>>b>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='a'){
			if(m<a+b){
				cout<<"Yes"<<endl;
				m++;
			}
			else{
				cout<<"No"<<endl;
			}
		}
		if(s[i]=='b'){
			if(m<a+b && l<b){
				cout<<"Yes"<<endl;
				m++;
				l++;
			}
			else{
				cout<<"No"<<endl;
			}
		}
		if(s[i]=='c'){
			cout<<"No"<<endl;
		}
	}
}


Measured memory_bytes: 896
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const int mod=1e9+7;
int p[N],inv[N];
// int ans[N];
int qmi(int a,int b)
{
    int ans=1;
    while(b){
        if(b&1)ans=((ll)ans*a)%mod;
        a=(ll)a*a%mod;
        b>>=1;
    }
    return ans;
}
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int f[N];
int sz[N];
void dfs1(int u,int fa)
{
    sz[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa)continue;
        dfs1(j,u);
        sz[u]+=sz[j];
    }
    f[u]=p[sz[u]-1];
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa)continue;
        f[u]=(ll)f[u]*inv[sz[j]]%mod*f[j]%mod;
    }
}
int n;
int g[N],ans[N];
void dfs2(int u,int fa)
{
    ans[u]=(ll)f[u]*inv[sz[u]-1]%mod*p[n-1]%mod*inv[n-sz[u]]%mod*g[fa]%mod;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa)continue;
        g[u]=(ll)ans[u]*inv[n-1]%mod*p[n-sz[j]-1]%mod*qmi(f[j],mod-2)%mod*p[sz[j]]%mod;
        // g[u]=f[u]*inv[sz[u]-1]%mod*p[n-sz[j]-1]%mod*p[sz[j]]%mod*qmi(f[j],mod-2)%mod*g[fa]%mod*inv[n-sz[u]]%mod;
        dfs2(j,u);
    }
}
int main()
{
//    int n;
    cin>>n;
    p[0]=1,inv[0]=1;
    for(int i=1;i<=n;i++)p[i]=(ll)p[i-1]*i%mod;
    for(int i=1;i<=n;i++)inv[i]=(ll)inv[i-1]*qmi(i,mod-2)%mod;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs1(1,1);
    g[0]=1;
    dfs2(1,0);
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
    return 0;
}

Measured memory_bytes: 10880
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> a;
ll sum;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    if (n > 1) {
        sum += a[n - 1];
    }
    int k = n - 2;
    for (n = n - 2; n >= 2; k--, n -= 2) {
        sum += a[k] * 2;
    }
    if (n == 1) {
        sum += a[k];
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 4224
// unolight {{{
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(c) begin(c),end(c)
#define REP(i,n) for ( int i=0; i<(int)(n); i++ )
#define REP1(i,a,b) for ( int i=(int)(a); i<=(int)(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long LL;

void RI() {}

template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d",&head);
    RI(tail...);
}

template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) _dump(#__VA_ARGS__, __VA_ARGS__);

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }

// }}}
const int MAX_N = 3005;
string S, T;
int dp[MAX_N][MAX_N];
int dir[MAX_N][MAX_N];
void input() {
    cin >> S >> T;
}

void solve() {
    int n = S.length(), m = T.length();

    REP1(i, 1, n) {
        REP1(j, 1, m) {
            if(S[i-1] == T[j-1]) {
                dp[i][j] = dp[i-1][j-1]+1;
                dir[i][j] = 3;
            } else {
                if(dp[i-1][j] > dp[i][j-1]) {
                    dp[i][j] = dp[i-1][j];
                    dir[i][j] = 1;
                } else {
                    dp[i][j] = dp[i][j-1];
                    dir[i][j] = 2;                    
                }
            }
        }
    }
    // cout << dp[n][m] << endl;
    // backtrack
    int i = n, j = m;
    string ans = "";
    while(i>0 && j>0) {
        if(dir[i][j] == 1) {
            i--;
        } else if(dir[i][j] == 2) {
            j--;
        } else {
            ans = S[i-1] + ans;
            i--; j--;
        }
    }

    cout << ans << endl;
}

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


Measured memory_bytes: 70784
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <iterator>      //集合演算(積集合,和集合,差集合など)
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列
#define CO(a, b, c) ((a) ? (b) : (c))
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
typedef long long ll;

int main(void)
{

    char s;
    cin >> s;
    if (isupper((int)s))
    {
        cout << 'A';
    }
    else
    {
        cout << 'a';
    }
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>

using namespace std;

int n;

int head[200010], to[400010], nxt[400010], cnt;

inline void AddEdge (int u, int v) { ++cnt, to[cnt] = v, nxt[cnt] = head[u], head[u] = cnt; }

long long ans;

inline void Dfs (int u, int p) {
	for (int e = head[u]; e; e = nxt[e]) {
		int v = to[e];
		if (v == p) continue;
		if (v < u) ans += 1ll * v * (u - v);
		else ans += 1ll * (v - u) * (n - v + 1);
		Dfs (v, u);
	}
}

int main () {
	scanf ("%d", &n);
	for (int i = 1; i < n; ++i) {
		int u, v; scanf ("%d%d", &u, &v);
		AddEdge (u, v), AddEdge (v, u);
	}
	
	Dfs (1, 0);
	
	printf ("%lld\n", ans + n);
	
	return 0;
}

Measured memory_bytes: 16820
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
int main()
{
	int t;
	t=1;
	while(t--)
	{
	int n;
	cin>>n;
	int arr[n];
	ll p=1000;
	long long int z;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}	
	for(int i=1;i<n;i++)
	{
       if(arr[i]>arr[i-1])
       {
        z=p/arr[i-1];
        p=p+z*(arr[i]-arr[i-1]);
       }
		
    }
    cout<<p<<endl;
	}
}


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

ll dig(ll n) {
  ll res = 0;
  while(n > 0) {
    res++;
    n /= 10;
  }
  return res;
}

ll f(ll a, ll b) {
  return max(dig(a), dig(b));
}

vector<ll> enum_div(ll n) {
  vector<ll> ret;
  for(ll i = 1; i*i <= n; i++) {
    if(n%i == 0) {
      ret.push_back(i);
    }
  }
  return ret;
}

int main() {
  ll n;
  cin >> n;
  ll ans = 100000000000;
  vector<ll> vec;
  vec = enum_div(n);
  rep(i,vec.size()) {
    ll a = f(vec.at(i), n/vec.at(i));
    ans = min(ans, a);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256