akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cstring>
#include<cstdio>
#include <cmath>
using namespace std;


int main()
{
	int a, b, ans;

	cin >> a >> b;

	ans = (a + b) / 2;

	if ((a + b) % 2 == 1)
		ans++;

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cctype>
using namespace std;
 
#define MD 1000000007
typedef long long int ll;

int main(){
    string s,t;
    cin>>s>>t;
    sort(s.begin(),s.end());
    sort(t.rbegin(),t.rend());
    if(s<t){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 50005

int N,M;
string WORD[NUM],rev_WORD[NUM];

int calc(const string slate){

	int left,right;
	string pattern = slate;

	if(pattern[pattern.length()-1] == '*'){

		pattern = pattern.substr(0,pattern.length()-1);
		left = lower_bound(WORD,WORD+N,pattern)-WORD;
		pattern.push_back('z'+1);
		right = lower_bound(WORD,WORD+N,pattern)-WORD;
		return right-left;

	}else if(pattern[0] == '*'){

		pattern = pattern.substr(1);
		reverse(pattern.begin(),pattern.end());
		left = lower_bound(rev_WORD,rev_WORD+N,pattern)-rev_WORD;
		pattern.push_back('z'+1);
		right = lower_bound(rev_WORD,rev_WORD+N,pattern)-rev_WORD;
		return right-left;

	}else{

		left = lower_bound(WORD,WORD+N,pattern)-WORD;
		if(WORD[left] == slate){
			return 1;
		}else{
			return 0;
		}

	}
}


int main(){

	scanf("%d %d",&N,&M);

	getchar();

	for(int i = 0; i < N; i++){
		getline(cin,WORD[i]);
		rev_WORD[i] = WORD[i];
		reverse(rev_WORD[i].begin(),rev_WORD[i].end());
	}
	sort(WORD,WORD+N);
	sort(rev_WORD,rev_WORD+N);

	string slate;
	int loc,ans;

	for(int loop = 0; loop < M; loop++){
		getline(cin,slate);

		loc = -1;

		for(int i = 0; i < slate.length(); i++){
			if(slate[i] == '?'){
				loc = i;
				break;
			}
		}

		if(loc == -1){
			printf("%d\n",calc(slate));
			continue;
		}

		ans = 0;
		for(int i = 0; i < 26; i++){
			slate[loc] = 'a'+i;
			ans += calc(slate);
		}

		printf("%d\n",ans);
	}

	return 0;
}



Measured memory_bytes: 12348
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
   int n;
   int P[100];
   int count = 0;

    cin >> n;
   for(int i = 0; i < n; i++){
       cin >> P[i];
   } 
   
   int naka;
   int temp[3];

   for (int j = 0; j <= (n - 3); j++){
       for(int k = 0; k < 3; k++){
            temp[k] = P[j+k];
            if(k == 1){
                naka = temp[k];
            }
       }
       sort(temp, temp+3);
       if(temp[1] == naka){
            count++;
       }
   }

   cout << count << endl;

}

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

typedef long long ll;
ll dp[100006][13];
int main()
{
    
    string s;
    cin>>s;
    for(int i=0;i<=s.size();i++) for(int j=0;j<13;j++) dp[i][j]=0;
    dp[0][0]=1;
    for(int i=0;i<s.size();i++){
        for(int j=0;j<13;j++){
            if(dp[i][j]!=0) {
                if(s[i]=='?'){
                    for(int x=0;x<=9;x++){ dp[i+1][((10*j)+x)%13]+=dp[i][j]%mod; dp[i+1][((10*j)+x)%13]%=mod; }
                }
                else {
                    ll val= (10*j)+s[i]-'0'; val%=13;
                    dp[i+1][val]+=dp[i][j]; dp[i+1][val]%=mod;
                }
            }
        }
    }
    cout<<dp[s.size()][5]%mod<<endl;
    
}

Measured memory_bytes: 10624
n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

for i in range(m):
    for j in range(2):
        C[i][j] -= 1

s0 = C[0][0]
s1 = C[0][1]

M = [[] for i in range(n)]
for i in range(m):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])

# 0-indexedの場合
V = [0] * n
V[s0] = 1
V[s1] = 1

# print("M",M)

ng = 0
s = s0
S0 = [s0]
while ng == 0:
    ng = 1
    for i in M[s]:
        if V[i] == 0:
            V[i] = 1
            ng = 0
            s = i
            S0.append(i)
            break
# print(V)

s = s1
S1 = [s1]
ng = 0
while ng == 0:
    ng = 1
    # print(M[s])
    for i in M[s]:
        if V[i] == 0:
            V[i] = 1
            ng = 0
            s = i
            S1.append(i)
            break
# print(S0, S1)
ANS = S1[::-1] + S0
for i in range(len(ANS)):
    ANS[i] += 1
print(len(ANS))
print(*ANS)

Measured memory_bytes: 81496
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const long double EPS = 1e-9;
const ll mod = 1e9 + 7;
const ll INF = 1e9;

#define rep(i, n) for(ll i = 0; i < n ; i++ )
#define For(i, a, b) for(ll i = (a); i < (b) ; i++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const ll MAX_N = 200000;

int main(void){
    ll N;
    ll A[MAX_N];
    ll L[MAX_N + 1], R[MAX_N + 1];
    ll answer = INF;

    /*
    after sorting in ascending order...
    A[i] <= b <= A[i + 1]
    f = (A[i + 1] - A[i])
      + (A[i + 2] - A[i - 1])
      + (A[i + 3] - A[i - 2])
      ...
      + (A[N - 1] - A[k]) or (A[k] - A[0])
      - (A[k - 1] + ... + A[0]) + b * k or + (A[N - 1] + ... + A[k + 1]) - b * .
    f = 
    */

    cin >> N;
    rep(i, N){
        cin >> A[i];
        A[i] -= i + 1;
    }

    sort(A, A + N);
    
    L[0] = 0;
    R[0] = 0;
    rep(i, N){
        L[i + 1] = L[i] + A[i];
        R[i + 1] = R[i] + A[N - i - 1];
    }

    answer = min(R[N] - L[0] - A[0] * N, R[0] + A[N - 1] * N - L[N]);

    For(i, 1, N){
        ll cnt = R[N - i] - L[i];
        ll c = 2 * i - N;
        answer = min({answer, cnt + c * A[i], cnt + c * A[i - 1]});
    }

    cout << answer << endl;

    return 0;
}

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

#include <iostream>
#include <vector>
// #include <map>
// #include <string>
// #include <algorithm>
// #include <numeric>
// #include <limits>

using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int cnt = 0;
	for (int i = a; i <= b; i++) {
		if (c % i == 0) {
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}



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

int main() {
  int H,W,N;
  cin >> H >> W >> N;
  vector<int>data(N);
  for(int i=0;i<N;i++){
    cin >> data.at(i);
  }
  vector<int>res;
  for(int i=0;i<N;i++){
    for(int j=0;j<data.at(i);j++){
      res.push_back(i+1);
    }
  }
  vector<vector<int>>ans(H,vector<int>(W));
  int x=0;
  for(int i=0;i<H;i++){
    if(i%2==0){
      for(int j=0;j<W;j++){
        ans.at(i).at(j)=res.at(x);
        x++;
      }
    }else{
      for(int j=W-1;j>=0;j--){
        ans.at(i).at(j)=res.at(x);
        x++;
      }
    }
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cout << ans.at(i).at(j) << " ";
    }
    cout << endl;
  }
}

Measured memory_bytes: 3716
import std.stdio, std.conv;
import std.array, std.algorithm, std.range;

void main()
{
    immutable int[dchar] L = ['I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000];
    foreach(w;stdin.byLine())
    {
        int s=0,t=0,c=0;
        foreach(n;w.map!(a=>L[a])())
        {
            if(n==c) t+=c;
            if(n>c) s-=t,t=c=n;
            if(n<c) s+=t,t=c=n;
        }
        writeln(s+t);
    }
}

Measured memory_bytes: 1044
#include <bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using pll = pair<ll,ll>;
using vll = vector<pll>;
#define ff first
#define ss second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define per(i,n) for(int i = (n)-1; i >= 0; --i)

int main() {
    int n; cin >> n;
    vll x(n);
    vl ans(n*n, 0);
    queue<pll> r, l;
    rep(i,n) {
        cin >> x[i].ff;
        x[i].ss = i+1;
        ans[x[i].ff-1] = i+1;
    }
    sort(x.begin(), x.end());
    rep(i,n) if (x[i].ss > 1) l.push(pll(x[i].ss, x[i].ss-1));
    per(i,n) if (x[i].ss < n) r.push(pll(x[i].ss, n-x[i].ss));
    auto f = [&](int i, queue<pll> &que) {
        if (que.empty()) return;
        if (ans[i] == 0) {
            ans[i] = que.front().ff; que.front().ss--;
            if (que.front().ss == 0) que.pop();
        }
    };
    rep(i,n*n) f(i,l);
    per(i,n*n) f(i,r);

    int pos = 1;
    vl cnts(n+1,0);
    rep(i,n) {
        while (pos < x[i].ff) cnts[ans[pos-1]]++, pos++;
        if (cnts[x[i].ss] < x[i].ss-1) {
            cout << "No" << endl;
            return 0;
        }
    }
    pos = n*n;
    cnts.assign(n+1,0);
    per(i,n) {
        while (x[i].ff < pos) cnts[ans[pos-1]]++, pos--;
        if (cnts[x[i].ss] < n-x[i].ss) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    rep(i,n*n) {
        cout << ans[i] << " \n"[i==n*n-1];
    }
    return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  int t;
  for(int i = 0; i < N; i++) {
    cin >> a.at(i);
    //cout << a.at(i) << ":" << i << endl;
  }
  int j = 0;
  while(j < N) {
    //cout << j << endl;
    if(j == 1) {
      cout << t << endl;
      break;
    }
    
    if(t > N) {
      cout << "-1" << endl;
      break;
    }
    
    j = a.at(j) - 1;
    t += 1;
  }
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  int sum=0;
  cin >> n;
  vector<int> l(n);
  for (int i=0; i<n; i++){
    cin >> l[i];
  }
  sort(l.begin(),l.end());
  int max = l[n-1];
  for (int i=0; i<n-1; i++){
    sum += l[i];
  }
  if (max<sum){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


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


/*
  let's try computer shogi!!!
 */

int main(){
  string str;
  cin >> str;
  if(str.size() < 4){cout<<"No"; return 0;}
  if(str[0]=='Y' && str[1]=='A' && str[2]=='K' && str[3]=='I' ){
    cout<<"Yes";
  }else{
    cout<<"No";
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h> 
int main(){
 int i,j,a[4],s=0,c[4][4],s1,s2,l=0;
 for(i=1;i<=3;i++)
 for(j=1;j<=3;j++)scanf("%d",&c[i][j]);
s1=c[2][1]-c[1][1];
s2=c[3][1]-c[2][1];
if(c[2][2]-c[1][2]==s1)l++;
if(c[3][2]-c[2][2]==s2)l++;
 if(c[2][3]-c[1][3]==s1)l++;
if(c[3][3]-c[2][3]==s2)l++;
if(l==4)printf("Yes");
    else printf("No");
	return 0;
	
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
# define pll pair<ll,ll>

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int a,b,c,k;
	cin>>a>>b>>c>>k;
	 int cnt=0;
	 while(b<=a){
	 	b=b*2;
	 	++cnt;
	 }
	 while(c<=b){
	 	c=c*2;
	 	++cnt;
	 }   
	 if(cnt>k)
	 cout<<"No";
	 else
	 cout<<"Yes";
    return 0;
}

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

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

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

  int res = k;
  for (int i = 0; i < n - 1; ++i) res *= k - 1;
  cout << res << "\n";
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int n,a[N];
ll res;
void Init()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
}
void Solve()
{
	for(int i=1;i<=n;i++)
	{
		res+=a[i]-1;
	}
}
void Print()
{
	printf("%lld\n",res);
}
int main()
{
	Init();
	Solve();
	Print();
	return 0;
}


Measured memory_bytes: 256
#include <cassert>
#include <array>
#include <algorithm>
#include <iostream>
#include <complex>
#include <vector>
using namespace std;

const double EPS = 1e-10;
template<class T>
bool eq(const T& a, const T& b) {return abs(a - b) < EPS;}

typedef complex<double> point;

namespace std {
	bool operator==(const point &a, const point &b){
		return eq(a, b);
	}
	bool operator<(const point& a, const point& b) {
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
}

double cross(const point& a, const point& b) {
	return imag(conj(a)*b);
}
double dot(const point& a, const point& b) {
	return real(conj(a)*b);
}

typedef array<point, 2> line;

bool intersectLL(const line& l, const line& m) {
	return !eq(cross(l[1]-l[0], m[1]-m[0]), 0.) || // non-parallel
			eq(cross(l[1]-l[0], m[0]-l[0]), 0.);   // same line
}

point crosspoint(const line& l, const line& m) {
	double A = cross(l[1] - l[0], m[1] - m[0]);
	double B = cross(l[1] - l[0], l[1] - m[0]);
	if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
	if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
	return m[0] + B / A * (m[1] - m[0]);
}

vector<line> lines;

int hitCount(const line& s) {
	vector<point> hits;
	for (const auto& t : lines) {
		if (intersectLL(s, t)) {
			point p = crosspoint(s, t);
			if (-100 < p.real() && p.real() < 100 && -100 < p.imag() && p.imag() < 100) {
				hits.push_back(p);
			}
		}
	}
	sort(hits.begin(), hits.end());
	auto it = unique(hits.begin(), hits.end());
	return it - hits.begin();
}

int main() {
	int n;
	while (cin >> n, n) {
		int cnt = 1;
		lines.clear();
		for (int i = 0; i < n; i++) {
			line l;
			for (auto& p : l) {
				int x, y;
				cin >> x >> y;
				p = point(x, y);
			}
			cnt += hitCount(l) + 1;
			lines.push_back(l);
		}
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 1232
#include <iostream>
#include <algorithm>
#include <string>
#include<vector>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int ans = 0;
    for (int i = a; i <= b; i++) {
        if ((i / 10000 == i % 10) && (i / 1000)%10 == i /10%10) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int minv=sc.nextInt();
		int maxv=-1000000000;
		for(int j=1; j<n; j++){
			int x=sc.nextInt();
			maxv=max(maxv,x-minv);
			minv=min(minv,x);
		}
		System.out.println(maxv);
	}
	public static int max(int x,int y){
		if(x>y){
			return x;
		}else{
			return y;
		}
	}
	public static int min(int x,int y){
		if(x<y){
			return x;
		}else{
			return y;
		}
	}

	}


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

int main() {
  int N, X;
  cin >> N >> X;
  int L[N + 1], D[N + 2];
  int cnt = 0;

  for (int i = 1; i <= N; i++) {
    cin >> L[i];
  }

  D[1] = 0;
  for (int i = 2; i <= N + 1; i++) {
    D[i] = D[i - 1] + L[i - 1];
  }

  for (int i = 1; i <= N + 1; i++) {
    if (D[i] <= X) cnt++;
  }

  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

#define ll long long
#define int long long
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define pb push_back
#define eb emplace_back
#define Size(v) (int)v.size()

using namespace std;
// using namespace __gnu_pbds;

int n, ans;

void solve() {
	cin >> n;

	FOR (i, 1, n - 1) {
		int u, v; cin >> u >> v;

		if (u > v) swap(u, v);

		// edges
		ans -= u * (n - v + 1);
	}

	// vertices

	FOR (i, 1, n) {
		ans += i * (n - i + 1);
	}

	cout << ans;
}

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

	int t = 1;
	while (t--) 
		solve();
	return 0;
}

Measured memory_bytes: 3620
import Foundation

let targets: [String] = ["eraser", "erase", "dreamer", "dream"]


func main() {
	var input = readLine()!
	for i in 0..<targets.count {
		if input.isEmpty { break }
		input = input.replacingOccurrences(of: targets[i], with: "")
	}
	print(input.isEmpty ? "YES" : "NO")
}

main()

Measured memory_bytes: 15600
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

bool less_deadline(pair<int, int> prev, pair<int, int> next);

bool less_deadline(pair<int, int> prev, pair<int, int> next){
    return prev.second < next.second;
}


int main(void)
{
    int job_count;
    vector<pair<int, int> > times;

    cin >> job_count;

    for(int i = 0; i < job_count; i++){
        pair<int, int> t;
        int req, lim;
        cin >> req >> lim;
        t = make_pair(req, lim);
        times.push_back(t);
    }

    sort(times.begin(), times.end(), less_deadline);

    long long accum_time = 0;
    for(int i = 0; i < job_count; i++){
        accum_time += times[i].first;
        if(accum_time > times[i].second){
            cout << "No" << endl; 
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}

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

#define ALL(a) (a).begin(), (a).end()
#define ll long long

using namespace std;


signed main(){
	ll n; cin >> n;
	map<ll, ll> a;
	set<ll> ans;
	for(ll i = 3; i < 10; i++){
		for(ll j = 1; i-j >= 0; j++){
			for(ll k = 1; i-(j+k) >= 0; k++){
				for(ll l = 1; i-(j+k+l) >= 0; l++){
					a[3] = j; a[5] = k; a[7] = l;
					vector<ll> tmp;
					for(auto e : a){
						for(ll m = 0; m < e.second; m++){
							tmp.push_back(e.first);
						}
					}
					do{
						ll t = 0;
						for(ll e = 0; e < tmp.size(); e++, t *= 10){
							t += tmp[e];
						}
						t /= 10;
						//cerr << t << endl;
						ans.insert(t);
					}while(next_permutation(ALL(tmp)));
				}
			}
		}
	}
	int ss = 0;
	for(auto itr = ans.begin(); itr != ans.end() && *itr <= n; ++itr){
		ss++;
	}
	cout << ss << endl;
							





	return 0;
}



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

int main(){
  int N;
  cin >> N;
  if (N / 10 % 111 == 0 || N % 1000 % 111 ==0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 256
import math
n,m=map(int,input().split())
if abs(n-m)>=2:
  print(0)
elif n==m:
  print((math.factorial(n)%1000000007)**2*2%1000000007)
else:
  print((math.factorial(n)%1000000007)*(math.factorial(m)%1000000007)%1000000007)

Measured memory_bytes: 4104
#include <cstdio>
using namespace std;
int main() {
	int a, b, c;
	int d=0;
	// while (true) {
		scanf("%d %d %d", &a, &b, &c);
		for (int i=a; i <= b; i++) {
			if (c%i == 0) {
				d++;
			}
		}
			printf("%d\n", d);
		
	// }
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	float n;
	cin>>n;
	float answer=2.0000 * 3.14159 * n;
	printf("%.3f",answer);
	return 0;
}

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

int main() {
    int n,x,t;
    cin >> n >> x >>t;
    
    int count=0;
    int num;
    
    if(n%x!=0) num = n/x+1;
    else num = n/x;

    cout << num*t << endl;
	
	return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define all(container) container.begin(),container.end()
#define fast ios::sync_with_stdio(0); cin.tie(0)
// #ifndef ONLINE_JUDGE
// #include "debug.cpp"
// #endif
#define int long long
const int mod = 1e9+7;  
int power(int a,int b) { if(b==0) return 1; int res = power(a,b/2); if(b&1) return res * res * a; else return res * res; }


int32_t main(){
    
  fast;

  int n; cin >> n;
  string s; cin >> s;

  for(int i=0;i<s.size();i++){
    int k = (s[i] - 'A' + n)%26;
    s[i] = 'A' + k;
  }

  cout << s;


  return 0;
}

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

int l;
typedef pair<int,int> pii;
vector<pii> data;
void init(){
  data.clear();
}


bool input(){
  if(!(cin>>l))return false;
  if(l==0)return false;
  for(int i=0;i<12;i++){
    int m,n;
    cin>>m>>n;
    data.push_back(pii(m,n));
  }
  return true;
}

int  solve(){
  int m=0;
  for(int i=0;i<data.size();i++){
    m+=max(0,data[i].first-data[i].second);
    if(!(m<l)){
      return i+1;
    }
  }
  return -1;
}

int main(){
  while(init(),input()){
    int ans= solve();
    if(ans==-1){
      cout<<"NA"<<endl;
    }else{
      cout<<ans<<endl;
    }
  }
}

Measured memory_bytes: 1196
//  ??????  ??????????????????
#include <iostream>
using namespace std;

int main(){
    int n;
 
    int H[101];
    int T[101];
    while(1){
        cin >> n;
        int C=0;
        
        if(n==0) break;
        for(int i=0; i<n; i++){
            cin >> T[i];
        }
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                if(T[i] > T[j]) swap(T[i],T[j]);
            }
        }
        int s=0;
        for(int i=1; i<=2*n; i++){
            for(int j=0; j<n; j++){
                if(i==T[j])
                    break;
                else if(j==n-1){
                    H[s++] = i;
                }
            }
        }

        int t=0;
        int n_t = n, n_h = n;
        while(!(n_t==0) && !(n_h==0)){
            for(int i=0; i<n; i++){
                if(T[i]>C){
                    C = T[i];
                    T[i]=0;
                    n_t--;
                    break;
                }else if(i==n-1){
                    C = 0;
                }
            }
            if(n_t==0 || n_h==0) break;
            for(int i=0; i<n; i++){
                if(H[i]>C){
                    C = H[i];
                    H[i]=0;
                    n_h--;
                    break;
                }else if(i==n-1){
                    C = 0;
                }
            }
            t++;
        }
        cout << n_h << endl;
        cout << n_t << endl;
    }
}

Measured memory_bytes: 3092
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define rt return
using dbl = double;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

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

    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;

    A *= 100; B *= 100;
    set<int> wa, su;
    for (int i = 0; i <= F; i += A)for (int j = i; j <= F; j += B) {
        wa.insert(j);
    }
    for (int i = 0; i <= F; i += C)for (int j = i; j <= F; j += D) {
        su.insert(j);
    }

    tuple<double, int, int> ma(0,A,0);
    each(w, wa)each(s, su) {
        if (w + s <= F && w / 100 * E >= s) {
            smax(ma, MT((dbl)s / (w + s), w + s, s));
        }
    }
    cout << get<1>(ma) << ' ' << get<2>(ma) << endl;
}


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

vector<char> A;
string input_str;

int main(){
    cin >> input_str;
    A.push_back('3');
    int str_length = input_str.length();
    for (int i = 0; i < str_length; i++){
        A.push_back(input_str[i]);
    }
    A.push_back('2');
    int count = 0;
    int idx = 0;
    char phand = A[0];
    char hand = A[1];
    while (true){
        // 終了条件
        idx += 1;
        hand = A[idx];
        if (hand == '2'){
            break;
        }
        if ((phand != hand) && (phand != '3')){
            A.erase(A.begin() + idx - 1);
            A.erase(A.begin() + idx - 1);
            idx -= 2;
            count += 2;
            phand = A[idx];
        }
        else{
            phand = hand;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int lcs (string x, string y) {

    int m, n, c[1001][1001], i, j, maxl = 0;

    m = x.size();
    n = y.size();

    x = ' ' + x;
    y = ' ' + y;

    for (i = 0; i <= m; i++) {
        c[i][0] = 0;
    }
    for (j = 1; j <= n; j++) {
        c[0][j] = 0;
    }

    for (i = 1; i <= m; i++) {
            for (j = 1; j <= n; j++) {

                if (x[i] == y[j]) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else {
                    c[i][j] = max (c[i - 1][j], c[i][j - 1]);
                }

                maxl = max (maxl, c[i][j]);

            }
    }

    return maxl;

}



int main () {

    int N, i;
    string x, y;

    cin >> N;

    for (i = 0; i < N; i++) {
        cin >> x >> y;
        cout << lcs (x, y) << endl;

    }

    return 0;

}

    

Measured memory_bytes: 7088
#include <cstdio>
#include <algorithm>
#include <cstring>
int main(){
	char a[1000],b[1000];
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	scanf("%s %s",a,b);
	strcat(b,a);
	printf("%s",b);
	return 0;
	}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+23;
char s[maxn];
int main(){
	scanf("%s",s);
	int now=0;
	for(int i=0;s[i];i++) now+=(s[i]-'0');
	puts(now%9?"No":"Yes");
}

Measured memory_bytes: 3872
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cassert>
#include <queue>
using namespace std;
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define fst first
#define snd second
#define SZ(x) ((int)x.size())
typedef long long ll;
#define dforn(i, n) for(int i = n - 1; i >= 0; i--)

const int MAXN = -1;

int a,b,c;
ll k;

int main() {
    //~ freopen("input.in", "r", stdin);
    while( scanf("%d%d%d%lld", &a,&b,&c,&k) >= 1 ){
        printf("%d\n", k%2?b-a:a-b);
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <queue>
#include <cmath>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 8e2+5, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, m, k, d[N][N], ans;
char s[N][N];
queue<pair<int, int> > q;
int min(int a, int b, int c, int d) { return min(a, min(b, min(c, d))); }
int main()
{
    n = read(), m = read(), k = read(), ans = n*m;
    for(int i = 1; i <= n; ++i) scanf("%s", s[i]+1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(s[i][j] == 'S') q.push(make_pair(i, j)), d[i][j] = 0;
            else d[i][j] = -1;
    while(q.size())
    {
        int x = q.front().first, y = q.front().second; q.pop();
        if(d[x][y] == k) continue;
        for(int i = 0; i < 4; ++i)
        {
            int nx = x+dx[i], ny = y+dy[i];
            if(d[nx][ny] == -1&&s[nx][ny] == '.') 
                d[nx][ny] = d[x][y]+1, q.push(make_pair(nx, ny));
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(d[i][j] != -1) ans = min(ans, 1+(int)ceil(1.0*min(i-1, j-1, n-i, m-j)/k));
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 3456
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<int> in(n);
  for (int i = 0; i < n; i++) {
    cin >> in[i];
  }
  string res;
  int open = 0;
  for (int i = 0; i < n; i++) {
    while (open < in[i]) {
      res += '(';
      open++;
    }
    res += ')';
  }
  stack<int> st;
  open = 0;
  int close = 0;
  for (int i = 0; i < n + n; i++) {
    if (res[i] == '(') st.push(++open);
    else {
      if (st.top() != in[close++]) {
        cout << ":(" << endl;
        return 0;
      }
      st.pop();
    }
  }
  cout << res << endl;
  return 0;	
}


Measured memory_bytes: 3888
import sys

def main():
    K = int(sys.stdin.readline().rstrip())

    A = [True] * K

    n = 7
    count = 1
    for i in range(K):
        n = n % K
        if n == 0:
            break
        n = n * 10 + 7
        count += 1
    
    if count > K:
        print(-1)
    else:
        print(count)

main()

Measured memory_bytes: 16748
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod = 998244353;
struct mint{
	ll x;
	mint(ll x = 0):x((x%mod+mod)%mod){}
	mint operator-() const{return mint(-x);}
	mint& operator+=(const mint a){
		if((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a){
		if((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a){
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const{
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const{
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const{
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const{
		if(!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if(t&1) a *= *this;
		return a;
	}
	mint inv() const{
		return pow(mod-2);
	}
	mint& operator/=(const mint a){
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const{
		mint res(*this);
		return res/=a;
	}
	bool operator==(const mint a){
		return x == a.x;
	}
};

mint dp[3005];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, s;
	cin >> n >> s;
	dp[0] = 1;
	rep(i,n){
		int a;
		cin >> a;
		for(int j = s; j >= 0; --j){
			if(j+a <= s) dp[j+a] += dp[j];
			dp[j] *= 2;
		}
	}
	cout << dp[s].x << endl;
	return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<long> P(N);
  for (long i = 0, sum = 0, p; i < N && cin >> p; i++) P.at(i) = sum += ++p;
  if (N == 1) return cout << fixed << setprecision(6) << (double)P.at(0) / 2 << "\n", 0;
  else if (N == K) return cout << fixed << setprecision(6) << (double)P.at(N - 1) / 2 << "\n", 0;
  long ma = 0;
  for (int i = 0; i + K < N; i++) ma = max(ma, P.at(i + K) - P.at(i));
  cout << fixed << setprecision(6) << (double)ma / 2 << "\n";
}

Measured memory_bytes: 1792
require 'pp'

N = readline.to_i
H = N.times.each.map do |i|
  readline.split.map(&:to_i)
end

dp = Array.new(N) { Array.new(3,0) }

dp[0][0] = H[0][0]
dp[0][1] = H[0][1]
dp[0][2] = H[0][2]

(1..(N-1)).each do |i|
  a = dp[i-1][0]
  b = dp[i-1][1]
  c = dp[i-1][2]
  dp[i][0] = H[i][0] + (b > c ? b : c)
  dp[i][1] = H[i][1] + (a > c ? a : c)
  dp[i][2] = H[i][2] + (b > a ? b : a)
end

puts dp[N-1].max


Measured memory_bytes: 12156
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
//#define unsigned long long ull


int main() {
  unsigned long long X, Y, x;
  cin >> X >> Y;

  int num = 0;
  x = X;
  while(x <= Y){
    num++;
    x *= 2;
  }

  cout << num << endl;

  return 0;
}

Measured memory_bytes: 256
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    t1, t2 = map(int, readline().split())
    a1, a2 = map(int, readline().split())
    b1, b2 = map(int, readline().split())

    if a1 < b1:
        a1, b1 = b1, a1
        a2, b2 = b2, a2

    if a2 > b2:
        return print(0)
    else:
        d1 = t1 * a1 + t2 * a2
        d2 = t1 * b1 + t2 * b2
        if d1 == d2:
            return print("infinity")
        elif d2 > d1:
            ans = 1
            diff = d2 - d1
            x = t1 * (a1 - b1)
            cnt = x // diff
            ans += cnt * 2
            if x % diff == 0:
                ans -= 1
            return print(ans)
        else:
            return print(0)


if __name__ == '__main__':
    main()


Measured memory_bytes: 61732
N=int(input())
if N<11 or N==12 or N==14 or N==15 or N==16 or N==18 or N==20 or N==21 or N==24 or N==25 or N==27 or N==28 or N==30 or N==32 or N==35 or N==36 or N==40 or N==42 or N==45 or N==48 or N==54 or N==56 or N==49 or N==63 or N==64 or N==72 or N==81:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include<stdio.h>

int main(void)
{
	int i;
	
	int n;
	scanf("%d",&n);
	
	int S[n];
	for(i=0;i<n;i++)
	{
		scanf("%d",&S[i]);
	}
	int q;
	scanf("%d",&q);
	
	int T[q];
	for(i=0;i<q;i++)
	{
		scanf("%d",&T[i]);
	}
	
	int count=0,x=0;
	
	for(i=0;i<q;i++)
	{
		x=T[i];
		int right=n,left=0;
		int mid=0;
		while(left<right)
		{
			mid=(left+right)/2;
			if(x==S[mid])
			{
				count++;
				break;
			}
			if(x>S[mid])
			{
				left=mid+1;
			}
			else if(x<S[mid])
			{
				right=mid;
			}
		}
	}
	
	printf("%d\n",count);
	
	return 0;
}


Measured memory_bytes: 2356
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max({a*c, a*d, b*c, b*d}) << endl;
}


Measured memory_bytes: 3648
n=int(input())
s=input()
a=["SS","SW","WS","WW"]
for i in range(n):
    for j in range(4):
        a[j]+="SW"[::-1 if s[i]=='o' else 1][a[j][i]==a[j][i+1]]
for i in range(4):
    if a[i][1]==a[i][n+1] and a[i][0] == a[i][n]:
        print(a[i][1:n+1])
        exit()
print(-1)


Measured memory_bytes: 3832
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int n, x;
    int[] as;

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

    void run() {
        FastReader sc = new FastReader();
        n = sc.nextInt();
        x = sc.nextInt();
        as = new int[n];
        for (int i = 0; i < n; i++) {
            as[i] = sc.nextInt();
        }
        solve();
    }

    void solve() {
        long count = 0;
        for (int i = 0; i < n - 1; i++) {
            if (as[i] + as[i + 1] > x) {
                count += as[i] + as[i + 1] - x;
                if (x <= as[i]) {
                    as[i] = x;
                    as[i + 1] = 0;
                } else {
                    as[i + 1] = x - as[i];
                }
            }
        }
        System.out.println(count);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 42624
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define NOT_FREE -1
#define FREE 0
#define N 8    


void putQueen(int);
void printBoard(void);


int x[N][N];
int col[N],row[N], dpos[ N*2-1 ], dneg[ N*2-1 ];
 
int main()
{
  int i, j, k, r, c;

  for( i = 0; i<N; i++ )
    row[i] = col[i] = FREE;
  for( i = 0; i<N*2-1; i++ )
    dpos[i] = dneg[i] = FREE;
  for( i = 0; i<N; i++ )
    {
      for( j = 0; j<N; j++ )
	x[i][j] = FALSE;
    }
    
  scanf("%d", &k);
  for( i = 0; i<k; i++ )
    {
      scanf("%d%d", &r, &c);
      x[r][c] = TRUE;
    }

  putQueen(0);

  return 0;
}

void putQueen(int i)
{
  int j;

  if( i == N )
    {
      printBoard();
      return;
    }

  for( j = 0; j<N; j++ )
    {  
      if( col[j] == NOT_FREE || dpos[ i+j ] == NOT_FREE || dneg[ i-j + N-1 ] == NOT_FREE )
	  continue;

      row[i] = j;
      col[j] = dpos[ i+j ] = dneg[ i-j + N-1 ] = NOT_FREE;
      
      putQueen( i+1 );

      row[i] = col[j] = dpos[ i+j ] = dneg[ i-j + N-1 ] = FREE;
    }
}

void printBoard(void)
{
  int i, j;

  for( i = 0; i<N; i++ )
    {
      for( j = 0; j<N; j++ )
	{
	  if( x[i][j] )
	    {
	      if( row[i] != j )
		return;
	    }
	}
    }

  for( i = 0; i<N; i++ )
    {
      for( j = 0; j<N; j++ )
	printf("%c", row[i] == j ? 'Q' : '.' );
      printf("\n");
    }
}


Measured memory_bytes: 2084
n = int(input())
a = list(map(int,input().split()))

seen = [0]*n
count = 0
for i in range(n):
  seen[a[i]-1] =  seen[a[i]-1] + 1

for i in range(n):
   if (seen[i] == 0) or (seen[i] == 1):
      continue
   count = count +seen[i]*(seen[i]-1)//2

for i in a:
  ans = count - (seen[i-1]*(seen[i-1]-1))//2 + ((seen[i-1]-2)*(seen[i-1]-1))//2
    
  print(int(ans))


Measured memory_bytes: 83788
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep4(i, a, b, c) for (int i = int(a), i##__b = int(b), i##__c = int(c); i < i##__b; i += i##__c)
#define rep1(n) rep4(i, 0, n, 1)
#define rep2(i, n) rep4(i, 0, n, 1)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define REP(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep3(i, a, b) for (int i = int(b) - 1, i##__a = int(a); i >= i##__a; i--)
#define rrep1(n) rrep3(i, 0, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep4(i, a, b, c) for (int i = int(a + (b - a - 1) / c * c), i##__a = int(a), i##__c = int(c); i >= i##__a; i -= i##__c)
#define RREP(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define FOR(i, x) for (auto &i : x)
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define mt make_tuple
const int MOD = 1e9 + 7;
const int INF = 1e9 + 9;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vbool = vector<bool>;
using vvbool = vector<vector<bool>>;
using vstring = vector<string>;
template <class T> using vv = vector<vector<T>>;
#define vvint(A, H, W) vvint A(H, vint(W))
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;}
// clang-format on
int main() {
    int n, x, y;
    cin >> n >> x >> y;
    x -= 1;
    y -= 1;
    vvint minof(n, vint(n, -1));
    REP(s, n) {
        queue<int> q;
        q.push(s);
        minof[s][s] = 0;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            if (now + 1 < n && minof[s][now + 1] == -1) {
                minof[s][now + 1] = minof[s][now] + 1;
                q.push(now + 1);
            }
            if (now - 1 >= 0 && minof[s][now - 1] == -1) {
                minof[s][now - 1] = minof[s][now] + 1;
                q.push(now - 1);
            }
            if (now == x && minof[s][y] == -1) {
                minof[s][y] = minof[s][now] + 1;
                q.push(y);
            }
            if (now == y && minof[s][x] == -1) {
                minof[s][x] = minof[s][now] + 1;
                q.push(x);
            }
        }
    }

    vint ans(10000);

    REP(i, n) {
        REP(j, i + 1, n) {
            ans[minof[i][j]] += 1;
        }
    }
    REP(i, 1, n) {
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 16000
# 相対的な座標
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
field = []
H, W = map(int, input().split())
for _ in range(H):
    field.append(list(input()))
for y in range(H):
    for x in range(W):
        if field[y][x] == '#':
            continue
        count = 0
        for k in range(8): # 8方向
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or W <= nx or ny < 0 or H <= ny: # 枠外
                continue
            if field[ny][nx] == '#':
                count += 1
        field[y][x] = str(count)
for h in range(H):
    print("".join(field[h]))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
long long a[100010];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%lld",&a[i]);
	int zero=0;
	for(int i=0;i<n;i++)if(a[i]==0)zero++;
	if(zero>0){
		printf("0\n");
		return 0;
	}
	long long prod=1;
	for(int i=0;i<n;i++){
		if(a[i]<=1000000000000000000/prod){
	prod*=a[i];
	}else{
		printf("-1\n");
		return 0;
		}
	}
	printf("%lld\n",prod);
}

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    ll N, A, B; cin >> N >> A >> B;
    ll res = 0;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];
    rep(i, N-1){
        ll tmp = a[i+1]-a[i];
        if(tmp*A > B) res += B;
        else res += tmp*A;
    }

    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


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

using ll = long long;
const ll INF = 1LL << 50;


 int main(void) {
int N, M;
cin >> N >> M;
const int NMAX = 1000;
 const int MMAX = 2000;
 int a[MMAX], b[MMAX];
 ll c[MMAX];

 for (int i = 0; i < M; ++i) {
 cin >> a[i] >> b[i] >> c[i];
 c[i] = -c[i];
 }

 ll dist[NMAX];

 for (int i = 0; i < N; ++i) {
dist[i] = INF;
 }

 dist[0] = 0;


for (int loop = 0; loop < N - 1; ++ loop) {
for (int i = 0; i < M; ++i) {
 if (dist[a[i] - 1] == INF) continue;

 if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
 dist[b[i] - 1] = dist[a[i] - 1] + c[i];
 }
 }
 }

 ll ans = dist[N - 1];


 bool negative[NMAX];

 for (int i = 0; i < N; ++i) {
 negative[i] = false;
 }

 for (int loop = 0; loop < N ; ++ loop) {
 for (int i = 0; i < M; ++i) {
if (dist[a[i] - 1] == INF) continue;

 if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
 dist[b[i] - 1] = dist[a[i] - 1] + c[i];
 negative[b[i] - 1] = true;
 }
 if (negative[a[i] - 1] == true) {
 negative[b[i] - 1] = true;
}
}
 }

 if (negative[N - 1])
 cout << "inf" << endl;
 else
 cout << -ans << endl;
}


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

int main()
{
	int N, D, X, A[105];
	int cnt = 0;
	cin >> N;
	cin >> D >> X;
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
	
	int day = 1;
	for (int i = 0; i < N; ++i) {
		day = 1;
		while (day <= D) {
			day += A[i];
			cnt++;
		}
	}

	cout << cnt + X << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A, B, C,D;

    cin >>A >>B >>C >>D;

    if(A+B>C+D){
        cout<<"Left"<<endl;
    }else if(A+B==C+D){
        cout<<"Balanced"<<endl;
    }else{
        cout<<"Right"<<endl;
    }
}

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

vector<int> v;

int main(){
	int n;
	cin >> n;
	v.resize(n);

	for(int i = 0; i < n; i++) cin >> v[i];

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

	int cnt = 0;
	int par = 0, sub = 0;
	while(par < n){
		int num = v[par];
		sub = 0;
		while(par < n and v[par] == num) sub++, par++;
		cnt += sub % 2;
	}

	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()

int main(){
	int N,K;
	cin>>N>>K;
	if(K>(N+1)/2){
		cout<<-1<<endl;
		return 0;
	}
	vector<tuple<int,int,int>> V(N);
	int S=(N+1)/2,L=S+N-1,M=2*N;
	for(int i=0;i<N;i++){
		get<1>(V[i])=L;
		get<2>(V[i])=M;
		get<0>(V[i])=L+M;
		
		L--;
		M--;
		if(M<S+N)M=S+2*N-1;
	}
	sort(all(V));
	for(int i=0;i<N;i++){
		get<0>(V[i])=K+2*N+i;
		get<1>(V[i])-=S-K;
		get<2>(V[i])-=S-K;
	}
	
	for(auto x:V){
		cout<<get<2>(x)<<" "<<get<1>(x)<<" "<<get<0>(x)<<endl;
	}
}


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

int main(){
  int N;
  int l, r;
  int total = 0;
  
  cin >> N;
  for(int i = 0;i < N; i++){
  	cin >> l >> r;
    total += r - l + 1;
  }
  cout << total << endl;
  return 0;
}

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

int main() {
  int N,M;
  cin >> N >> M;
  long x[N],y[N],z[N];
  vector<long> sum(N);
  long ans[8]={};
  for(int i=0;i<N;i++){
    cin >> x[i] >> y[i] >> z[i];
  }
  for(int j=0;j<8;j++){
    for(int i=0;i<N;i++){
      sum[i]=x[i]*(2*(j%2)-1)+y[i]*(2*((j/2)%2)-1)+z[i]*(2*((j/4)%2)-1);
    }
    sort(sum.begin(),sum.end());
    reverse(sum.begin(), sum.end());
    for(int i=0;i<M;i++){
      ans[j]+=sum[i];
    }
  }
  cout << max({ans[0],ans[1],ans[2],ans[3],ans[4],ans[5],ans[6],ans[7]});
}

Measured memory_bytes: 256