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

int swapCount;

// N 個の要素を含む 0-オリジンの配列 A
void selectionSort(int a[], int n){
    for(int i=0; i<n; i++){
        int minj = i;
        for(int j=i; j<n; j++){
            if(a[j] < a[minj]){
                minj = j;
            }
        }
        if(i != minj){
            swap(a[i], a[minj]);
            swapCount++;
        }
    }
}

void print(int a[], int n){
    for(int i=0; i<n-1; i++){
        cout << a[i] << " ";
    }
    cout << a[n-1] << endl;
}

int main(void){
    int n;
    cin >> n;
    int a[110];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    swapCount = 0;
    selectionSort(a, n);

    print(a, n);

    cout << swapCount << endl;
    return 0;
}


Measured memory_bytes: 3100
#include <iostream>
#include <string.h>
using namespace std;

int iskaibun(char* s, int start, int end)
{
    int flag = 1;
    
    for(int i = 0; i < (end-start+1)/2 && flag == 1; i++)
    {
        if(s[start+i] != s[end-i])
            flag = 0;
    }
    
    return flag;
}

int main(void){
    // Your code here!
    char S[100];
    scanf("%s", S);
    
    int N = strlen(S);
    
    printf("%s\n", (iskaibun(S, 0, N-1) * iskaibun(S, 0, (N-1)/2-1) * iskaibun(S, (N+3)/2-1, N-1) == 1)? "Yes":"No");
}


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

int main() {
	int mizu,kane,sa;
	kane=0;
	int n=1;
	while(n){
		
		cin >> mizu;
		
		if(mizu==-1) break;
		if(mizu>10 && mizu<=20){
			mizu=mizu-10;
			kane=1150+mizu*125;
		}else if(mizu>20 && mizu<=30){
			mizu=mizu-20;
			kane=1150+1250+mizu*140;
		}else if(mizu<=10){
			kane=1150;
		}else if(mizu>30){
			mizu=mizu-30;
			kane=1150+1250+1400+(mizu*160);
		}
		n++;
		cout << 4280-kane << endl;
		}
	
	return 0;
}

Measured memory_bytes: 3048
#include <bits/stdc++.h>
using namespace std;
int n,m,k,a[8][8],s,r;
bool l[8],c[8];
char ch;
void f(int x)
{ if(x==max(n,m)+1)
  { s=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        if(!l[i] && !c[j])
           s+=a[i][j];
    if(s==k)
       r++;
  }
  if(x<=n)
  { l[x]=1;
    c[x]=0;
    f(x+1);
    l[x]=0;
    c[x]=0;
    f(x+1);
    if(x<=m)
    { l[x]=0;
      c[x]=1;
      f(x+1);
      l[x]=1;
      c[x]=1;
      f(x+1);
    }
  }
  else
  { if(x<=m)
    { c[x]=0;
      f(x+1);
      c[x]=1;
      f(x+1);
    }
  }
  l[x]=c[x]=0;
}
int main()
{ cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin>>n>>m>>k;
  for(int i=1;i<=n;i++)
  { for(int j=1;j<=m;j++)
    { cin>>ch;
      if(ch=='#')
         a[i][j]=1,s++;
    }
  }
  if(s<k)
  { cout<<"0\n";
    return 0;
  }
  f(1);
  cout<<r<<'\n';
  return 0;
}


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

int main()
{
   int N, M, C;
   cin >> N >> M >> C;
   vector<int> B(M);
   for(int i = 0; i < M; i++)
    cin >> B[i];
   vector<vector<int>> A(N,vector<int>(M));
   for(int i = 0; i < N; i++)
   {
      for(int j = 0; j < M; j++)
      {
         cin >> A[i][j];
      }
   }
   int ans = 0;
   for(int i = 0; i < N; i++)
   {
      long long sum = C;
      for(int j = 0; j < M; j++)
      {
         sum += A[i][j]*B[j];
      }
      if(sum > 0)
         ans++;
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256
use std::io::*;

fn calc_lay_length_and_next_wh(w: u64, h: u64) -> ((u64, u64), u64) {
    if w >= h {
        let triangles = w / h;
        let w2 = w % h;
        let h2 = h;

        if w2 == 0 {
            return ((0, 0), h * (2 * triangles - 1));
        } else {
            return ((w2, h2), 2 * h * triangles);
        }
    } else {
        let triangles = h / w;
        let w2 = w;
        let h2 = h % w;

        if h2 == 0 {
            return ((0, 0), w * (2 * triangles - 1));
        } else {
            return ((w2, h2), 2 * w * triangles);
        }
    }
}

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    let mut itr = buf.split_whitespace();
    let n: u64 = itr.next().unwrap().parse().unwrap();
    let x: u64 = itr.next().unwrap().parse().unwrap();

    let mut w = x;
    let mut h = n - x;
    let mut l = w + h;
    loop {
        let ((w_, h_), l_) = calc_lay_length_and_next_wh(w, h);
        w = w_;
        h = h_;
        l += l_;
        if w == 0 {
            break;
        }
    }

    println!("{}", l);
}


Measured memory_bytes: 380
#include <bits/stdc++.h>
using namespace std;
string s;
int l;
int main(){
    cin>>s;
    l=s.size();
    for(register int i=0;i<l;i++){
        if(s[i]=='C'){
            for(register int j=i+1;j<l;j++){
                if(s[j]=='F'){
                    cout<<"Yes"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

#define INF 2e9
#define INF_LL 1LL<<60
#define ll long long
#define MOD 1e9+7

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain; 

int main()
{
    int n;
    cin >> n;
    vector<int> vec(n);
    REP(i, n) cin >> vec[i];
    int ans = 0;

    REP(i, n) REPN(j, i+1, n) {
        ans += vec[i] * vec[j];
    }

    cout << ans << endl;

    return 0;
}

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

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

    vector<int> m(N+1);
    int S=0, M = 1000;
    for (int i=1; i<N+1; i++) {
        cin >> m.at(i);
        S += m.at(i);
        if (m.at(i) < M) {
            M = m.at(i);
        }
    }
    
    cout << N + (X - S)/M << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define MAX(a, b) (a>b?a:b)
#define MIN(a, b) (a<b?a:b)
#define MOD 1000000007

int compare(const void* a, const void* b) {
    return *(int*)a-*(int*)b;
}

void testCase() {
    int i, j, k, l;
    if(scanf("%d%d%d%d", &i, &j, &k, &l)) {
        while(1) {
            k -= j;
            if(k <= 0) {
                printf("Yes");
                break;
            }
            i -= l;
            if(i <= 0) {
                printf("No");
                break;
            }
        }
    }
}

int main() {
    int t;
    // scanf("%d", &t);
    // while(t--) {
    //     testCase();
    // }
    testCase();
    return 0;
}

Measured memory_bytes: 1728
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
 
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

int main() {

	string S; 
	cin >> S;

	for (char i = 'a'; i <= 'z'; i++) {
		if (S.find(i) == string::npos) {
			cout << i << endl;
			return 0;
		}
	}

	cout << "None" << endl;

    return 0;
}

Measured memory_bytes: 512
let [|n;k|] = stdin.ReadLine().Split() |> Array.map int64

// a=b=c=0(mod k) or a = b = c = k/2(modk)以外は条件を満たさない
if k%2L <> 0L then
    pown (n/k) 3
else
    pown (n/k) 3 + pown ((n+k/2L)/k) 3
|> stdout.WriteLine

Measured memory_bytes: 11220
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    public struct Pair { public int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } }
    public static void Solve()
    {
        int N = NextInt();
        long K = NextLong();
        List<int>[] G = Enumerable.Range(0, N + 1).Select(v => new List<int>()).ToArray();
        for (int i = 0; i < N - 1; i++)
        {
            int a = NextInt();
            int b = NextInt();
            G[a].Add(b);
            G[b].Add(a);
        }

        int[] rel = new int[N + 1];
        long[] col = Enumerable.Range(0, N + 1).Select(v => (long)-1).ToArray();

        Stack<int> S = new Stack<int>();
        S.Push(1);
        while (S.Count() != 0)
        {
            int now = S.Pop();
            int M = 0;
            rel[now]++;
            foreach (int e in G[now])
            {
                M += rel[e];
                rel[e]++;
                if (col[e] == -1) S.Push(e);
            }
            col[now] = (K - M);
            col[now] %= MOD;
        }
        long ans = 1;
        for (int i = 1; i <= N; i++) { ans *= col[i]; ans %= MOD; }
        Console.WriteLine(ans);
    }
    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }
}

public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
    public long Abs(long a, long b) => Math.Abs(a - b);
}


Measured memory_bytes: 31756
h, n = map(int, input().split())
magics = []
for i in range(n):
    a, b = map(int, input().split())
    magics.append((a, b))
h_table = [float("inf") for _ in range(h + 1)]
h_table[0] = 0
for i in range( h + 1):
    for a, b in magics:
        h_table[min(i + a, h)] = min(h_table[min(i + a, h)], h_table[i] + b)
print(h_table[h])


Measured memory_bytes: 43484
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <tuple>
#include <math.h>
#include <set>
#include <map>
using namespace std ;
using ll = long long ;
using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
using vb = vector<bool> ;
using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end() 
const ll INF = 1e18 ;
const ll mod = 998244353 ;
const double pie = acos(-1); 
vll dx4 = {-1,0,1,0} ;
vll dy4 = {0,-1,0,1} ;
vll dx8 = {-1,0,1,1,1,0,-1,-1} ;
vll dy8 = {-1,-1,-1,0,1,1,1,0} ; 

void fix_cout(){cout << fixed << setprecision(20) << endl ; }
ll gcd(ll a,ll b){if(b==0) return a ; return gcd(b,a%b) ; }
ll lcm(ll a,ll b){return a/gcd(a,b)*b ; }
void chmax(ll &a,ll b){if(a<b) a = b ; }
void chmin(ll &a,ll b){if(a>b) a = b ; }

ll modpow(ll a,ll b){
    ll res = 1 ;
    while(b>0){
        if(b&1) res = res*a%mod ;
        b >>= 1 ;
        a = a*a%mod ;
    }
    return res ;
}

int main(){
	ll n,s ;
	cin >> n >> s ;
	vvll dp(n+1,vll(s+1,0)) ;
	dp.at(0).at(0) = 1 ;
	for(int i=0;i<n;i++){
		ll a ; cin >> a ;
		for(int j=0;j<=s;j++){
			dp.at(i+1).at(j) = dp.at(i).at(j)*2%mod ;
			if(j>=a) dp.at(i+1).at(j) += dp.at(i).at(j-a) ;
			dp.at(i+1).at(j) %= mod ;
		}
	}
	cout << dp.at(n).at(s) << endl ;
}

Measured memory_bytes: 73680
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
using namespace std;

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


//ABC085_b
int main() {
	int N;
	cin >> N;

	set<int> ss;
	rep(i, N) {
		int s;
		cin >> s;
		ss.insert(s);
	}
	cout << ss.size() << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        char s[] = str1.toCharArray();
        char t[] = str2.toCharArray();
        int ans = 0;
        for(int i=0;i<s.length;i++)
        {
            if(s[i]!=t[i])
                ans++;
        }
        System.out.println(ans);
        
        
    }
}

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

int main() {
    int n;
    cin >> n;
    int m = n % 10;
    switch (m) {
        case 2:
        case 4:
        case 5:
        case 7:
        case 9:
            puts("hon");
            break;
        case 0:
        case 1:
        case 6:
        case 8:
            puts("pon");
            break;
        default:  // 3
            puts("bon");
            break;
    }

    return 0;
}

Measured memory_bytes: 3632
from collections import Counter
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, *v = map(int, read().split())

odd_c = Counter(v[0::2])
even_c = Counter(v[1::2])

odd_c = odd_c.most_common()
if len(odd_c) == 1:
    odd_c.append((0, 0))
even_c = even_c.most_common()
if len(even_c) == 1:
    even_c.append((0, 0))

if odd_c[0][0] != even_c[0][0]:
    ans = n - (odd_c[0][1] + even_c[0][1])
else:
    ans = n - (max(odd_c[1][1] + even_c[0][1], odd_c[0][1] + even_c[1][1]))
print(ans)


Measured memory_bytes: 25088
def main():
    N, M = map(int, input().split())
    ans = [1] * M
    for _ in range(N):
        A = list(map(lambda x: int(x) - 1, input().split()))[1:]
        for a in range(M):
            if a not in A:
                ans[a] = 0
    print(sum(ans))


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int mm = sc.nextInt();
        TreeMap<Integer, Integer> counts = new TreeMap<>();
        int start = sc.nextInt();
        int prev = start;
        for (int i = 1; i < mm; i++) {
            int x = sc.nextInt();
            if (counts.containsKey(x - prev)) {
                counts.put(x - prev, counts.get(x - prev) + 1);
            } else {
                counts.put(x - prev, 1);
            }
            prev = x;
        }
        if (counts.containsKey(n + 1 - prev)) {
            counts.put(n + 1 - prev, counts.get(n + 1 - prev) + 1);
        } else {
            counts.put(n + 1 - prev, 1);
        }
        int[] sums = new int[n + 1];
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            for (int i = 0; i < entry.getKey(); i++) {
                sums[i] += (entry.getKey() - i) * entry.getValue();
            }
        }
        int q = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            int x = sc.nextInt();
            if (x < start - 1) {
                sb.append(-1).append("\n");
                continue;
            }
            x -= start - 1;
            int left = 0;
            int right = n;
            while (right - left > 1) {
                int m = (left + right) / 2;
                if (sums[m] > x) {
                    left = m;
                } else {
                    right = m;
                }
            }
            sb.append(right).append("\n");
        }
        System.out.print(sb);
    }
}


Measured memory_bytes: 99836
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
int read(){
	int x=0,fh=1; char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') fh=-1;
	for (;isdigit(ch);ch=getchar()) x=x*10+(ch^48);
	return x*fh;
}
int a[200005],b[200005],c[200005],d[200005];
int main(){
	int n=read(),x=1,ans=0,aa,bb,cc,y; long long e;
	For(i,1,n) a[i]=read(); For(i,1,n) b[i]=read();
	For(_,1,29){
		For(i,1,n){
			y=a[i]; y>>=_; y<<=_; c[i]=a[i]-y;
			y=b[i]; y>>=_; y<<=_; d[i]=b[i]-y;
		}
		sort(c+1,c+1+n); sort(d+1,d+1+n); d[n+1]=1e9; e=0;
		aa=0; while(c[1]+d[aa]<x) ++aa;
		bb=aa; while(c[1]+d[bb]<x*2) ++bb;
		cc=bb; while(c[1]+d[cc]<x*3) ++cc; e=bb-aa+n-cc+1;
		For(i,2,n){
			while(c[i]+d[aa-1]>=x&&aa>1) --aa;
			while(c[i]+d[bb-1]>=x*2&&bb>1) --bb;
			while(c[i]+d[cc-1]>=x*3&&cc>1) --cc;
			e+=(bb-aa+n-cc+1);
		}
		if (e%2==1) ans|=(1<<(_-1)); x<<=1;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

double getDistance(double x, double y, double x2, double y2) {
  double distance = sqrt((x2 - x) * (x2 - x) + (y2 - y) * (y2 - y));

  return (double) distance;
}

int main() {

  int n;
  cin >> n;

  vector<int> x(n);
  vector<int> y(n);

  for(int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }

  double num = 1;
  for (int i = 1; i <= n; ++i)
  {
    num *= i;
  }
  double a = (n-1)*n/2;
  // それぞれの回数
  double s = num * (n-1) / a;
  // cout << s << endl;
  double sum = 0;
  for(int i = 0; i < n; i++) {
    for(int j = i+1; j < n; j++) {
      sum += getDistance(x[i],y[i],x[j],y[j]) * s;
    }
  }

  // cout << sum/num << endl;
  printf("%f\n",sum/num );
}


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

int digit(int n){
    int digitsum = 0;
    while(n){
        digitsum += n % 10;
        n = n / 10;
    }
    return digitsum;
}

int main(){
    int n;
    cin >> n;
    int ans = 1000000;
    for(int i = 1; i < n; i++){
        if(ans > digit(i) + digit(n-i)){
            ans = digit(i) + digit(n-i);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3616
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>

using namespace std;

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

	cin >> a >> b >> h;

	cout << (a + b)*h / 2 << endl;








	getchar();
	getchar();
	return 0;
}


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

    //static char[] xx = new char[] {'S','H','C','D'};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int box[][] = {{1,2,3,4,5,6,7,8,9,10,11,12,13},
        	{1,2,3,4,5,6,7,8,9,10,11,12,13},
        	{1,2,3,4,5,6,7,8,9,10,11,12,13},
        	{1,2,3,4,5,6,7,8,9,10,11,12,13}};

        for(int i = 0; i < n; i++) {
            String m = sc.next();
            int b = sc.nextInt();

            if(m.equals("S")) {
                box[0][b-1] = 0;
            }
            if(m.equals("H")) {
            	box[1][b-1] = 0;
            }
            if(m.equals("C")) {
            	box[2][b-1] = 0;
            }
            if(m.equals("D")) {
            	box[3][b-1] = 0;
            }
        }
        for(int i = 0 ; i< 4; i++) {
            for(int j = 0; j < 13; j++) {
                //if(!box[i][j]) {
            	if(box[i][j]!=0) {
            		if (i == 0)
                        System.out.println("S " + (j + 1));
                    else if (i == 1)
                        System.out.println("H " + (j + 1));
                    else if (i == 2)
                        System.out.println("C " + (j + 1));
                    else
                        System.out.println("D " + (j + 1));
            	}
            }
        }
        //System.out.println("");
    }
}


Measured memory_bytes: 26340
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int x,y,z;
    cin  >> x >>y;
    if(x>=13){
        z=y;
    }else if(x>5 && x<=12){
        z=y/2;
    }else{
        z=0;
    }
    cout << z << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int a,b,k;
    scanf("%d%d", &a,&b);

    int res= (a+b);
    if (res%2==0)
    {
        printf("%d\n", res/2);
    }else
    {
        printf("IMPOSSIBLE\n");
    }
    
    return 0;
}


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

// headers {{{
using namespace std;
// using namespace rel_ops;
 
const double pi=acos(-1.0);
const double eps=1e-11;
const int INF=0x7FFFFFFF;
template<class T> inline bool checkmin(T &a,T b){return b<a?a=b,1:0;}
template<class T> inline bool checkmax(T &a,T b){return b>a?a=b,1:0;}
template<class T> inline T sqr(T x){return x*x;}
template<class T> inline bool bit(T a, int b) {return (a>>b)&1;}
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(long long n) { return __builtin_popcountll(n); }
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define eb(args...) emplace_back(args)
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ff first
#define ss second
#define sz(g) int(g.size())
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
#ifdef LOCAL
#define dout cerr 
void out() { dout << endl; }
template<typename A, typename... B> void out(A a, B... b) { dout << ' ' << a; out(b...); }
#define dbg(args...) dout << __LINE__ << ":(" << #args << ") -> ", out(args)
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
constexpr bool local = true;
#else
#define dbg(...)
#define dout if(true);else cerr
#define out(...)
#define show(...)
constexpr bool local = false;
#endif
// }}}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    int n, k;
    while (cin >> n >> k) {
        VI a(n), b(n);
        rep(i, n) cin >> a[i];
        rep(t, k) {
            VII c;
            rep(i, n) {
                c.eb(i-a[i], 1);
                c.eb(i+a[i]+1, -1);
            }
            sort(c.begin(), c.end());
            int s = 0, k = 0;
            rep(i, n) {
                while (k < sz(c) && c[k].ff <= i) {
                    s += c[k].ss;
                    k++;
                }
                b[i] = s;
            }
            if (a == b) break;
            swap(a, b);
        }
        rep(i, n) cout << a[i] << ' ';
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 11924
#Colorful Leaderboard
N = int(input())
a = list(map(int, input().split()))
L = [0 for i in range(8)]
s = 0
for i in range(N):
    if a[i] < 3200:
        L[a[i]//400] = L[a[i]//400] + 1
    else:
        s = s + 1
n = 0
for i in range(8):
    if L[i] > 0:
        n = n + 1
nmin = n
nmax = n + s
if nmin == 0:
    nmin = 1
print(str(nmin)+" "+str(nmax))

Measured memory_bytes: 3064
r=range
M=[list(map(int,input().split())) for _ in r(3)]
for i in r(2):
  x=M[0][i]-M[0][i+1]
  y=M[i][0]-M[i+1][0]
  for j in r(3):
    if x!=M[j][i]-M[j][i+1] or y!=M[i][j]-M[i+1][j]:
      print('No')
      exit()
print('Yes')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
int dp[50][500][500];
int INF = 1e9;

signed main(){
  int n,ma,mb;
  cin>>n>>ma>>mb;
  vector<int> a(n),b(n),c(n);
  for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];

  for(int i=0;i<50;i++)
    for(int j=0;j<500;j++)
      for(int k=0;k<500;k++)
	dp[i][j][k]=INF;

  dp[0][0][0]=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<500;j++){
      for(int k=0;k<500;k++){
	if(dp[i][j][k]==INF) continue;
	dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]);
	dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i]);
      }
    }
  }

  int ans=INF;
  for(int j=1;j<500;j++)
    for(int k=1;k<500;k++)
      if(j*mb==k*ma)
	ans=min(ans,dp[n][j][k]);
  
  if(ans==INF) ans=-1;
  cout<<ans<<endl;
  return 0;
}


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

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


Measured memory_bytes: 384
;
import java.util.*;

public class Main {

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

	int INF = 1001001001;
	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int dp[][] = new int[n][n];
		int a[][] = new int[n][n];
		int tmp[][] = new int[n][n];
		for(int i=0; i<n ;i++) {
			for(int j=0; j<n; j++) {
				dp[i][j]=sc.nextInt();
				a[i][j]=dp[i][j];
				tmp[i][j]=dp[i][j];
			}
		}

		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				if(dp[i][k]==INF) continue;
				for(int j=0; j<n; j++) {
					if(dp[k][j]==INF) continue;
					if(dp[i][k] + dp[k][j] < a[i][j]) {
						System.out.println(-1);
						sc.close();
						return;
					}
					if(i != k && k != j && i != j && dp[i][k] + dp[k][j] == a[i][j]) {
						tmp[i][j]=INF;
					}
					dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
				}
			}
		}

		long ans = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(tmp[i][j] ==INF) continue;
				ans += tmp[i][j];
			}
		}
		System.out.println(ans/2);

		sc.close();
	}


}


Measured memory_bytes: 61132
#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 x = 1e9 + 7; 
const int INF = 1001001001;


int main() {
  string s;
  int q;
  cin >> s >> q;
  int flag = 1;
  string front = "", back = "";
  rep(i,q) {
    int t;
    cin >> t;
    if (t == 1) flag *= -1;
    if (t == 2) {
      int f;
      char sq;
      cin >> f >> sq;
      if (f*flag == 1 || f*flag == -2) front.push_back(sq);
      if (f*flag == 2 || f*flag == -1) back.push_back(sq);
    }
  }
  string ans;
  if (flag == -1) {
    reverse(s.begin(), s.end());
    reverse(back.begin(), back.end());
    ans = back + s + front;
  }
  else {
    reverse(front.begin(), front.end());
    ans = front + s + back;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4232
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT    \
    cin.tie(0); \
    ios::sync_with_stdio(false);

template <class T>
inline bool chmax(T& a, T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline bool chmin(T& a, T b) {
    return a = (a > b) ? b : a;
}

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

int main() {
    INIT;

    ll N;
    cin >> N;

    if (N % 10 == 2 || N % 10 == 4 || N % 10 == 5 || N % 10 == 7 ||
        N % 10 == 9) {
        cout << "hon" << endl;
    } else if (N % 10 == 0 || N % 10 == 1 || N % 10 == 6 || N % 10 == 8) {
        cout << "pon" << endl;
    } else {
        cout << "bon" << endl;
    }

    return 0;
}

Measured memory_bytes: 3640
a,b,m = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = min(a)+min(b)
for i in range(m):
    x,y,c = map(int, input().split())
    ans = min(ans,a[x-1]+b[y-1]-c)
print(ans)

Measured memory_bytes: 18736
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;

int main() {
	int H, W;
	while (true) {
		cin >> H >> W;
		if (H == 0 && W == 0)break;
		for (int h = 0; h < H; h++) {
			for (int w = 0; w < W; w++)
				if ((w + h) % 2)
					cout << ".";
				else
					cout << "#";
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int main(){
    int A, B, C, X;
    cin >> A >> B >> C >> X;
    int count = 0;
    for (int i = 0; i <= A; i++){
        for (int j = 0; j <= B; j++){
            for (int k = 0; k <= C; k++){
                if (500*i + 100*j + 50*k == X){
                    count++;
                }
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
n = int(input())
s = list(input())

def check(pin):
    a,b,c = pin[0],pin[1],pin[2]
    i=0
    count = 0
    for i in range(n):
        if count == 0 and s[i]==a:
            count += 1
        elif count == 1 and s[i]==b:
            count += 1
        elif count == 2 and s[i]==c:
            count += 1
            break
    if count == 3:
        return True
    else:
        return False

count = 0
for i in range(1000):
    pin = str(i)
    if len(pin) == 1:
        pin = "00"+pin
    elif len(pin) == 2:
        pin = "0"+pin
    if check(pin):
        count += 1        

print(count)

Measured memory_bytes: 42732
A = B = 0
team = "A"
n = int(input())
for i in range(n):
    cnt =  b1 = b2 = b3 = out = 0
    while out != 3:
        s = input()
        if s == "HIT":
            if b3 == 1:
                cnt+=1
            b1,b2,b3 = 1,b1,b2
        elif s == "HOMERUN":
            cnt+=b1+b2+b3+1
            b1 = b2 = b3 = 0
        elif s == "OUT":
            out+=1
            if out == 3 and team == "A":
                A+=cnt
                team="B"
                print(cnt)
            elif out == 3 and team == "B":
                B+=cnt
                team="A"
                print(cnt)


Measured memory_bytes: 5592
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')
# ----------------------------------------------------------- #

s = S()
zero = s.count("0")
one = s.count("1")
print(min(zero, one)*2)


Measured memory_bytes: 63980
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int A, B, C; cin >> A >> B >> C;
    cout << min(B / A, C) << nl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define N 100001
int DP[N] = {0};
vector<int> adj[N];
bool vis[N] = {0};

void dfs(int x)
{
    //d++;
    vis[x] =1;
    int k = INT_MIN;
    for(auto i:adj[x])
    {
        
        if(!vis[i])
        {
            dfs(i);
        }
        DP[x] = max(DP[x],1+DP[i]);
    }
    
}



signed main() {
    int n,m;
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        adj[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        dfs(i);}
    cout<<*max_element(DP+1,DP+n+1);
    //cout<<DP[5];
    return 0;
}

Measured memory_bytes: 8576
"use strict"
const create = () => {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
    const res = {
        "list": input, "index": 0, "max": input.length,
        "hasNext": function() {return this.index < this.max},
        "next": function() { if (!this.hasNext()) {throw "ArrayIndexOutOfBoundsException";}else{return this.list[this.index++];}}
    };
    return res;
}
const o = create();
const next = () => o.next()
const nextInt = () => parseInt(o.next())
const nextStrArray = () => o.next().split(" ")
const nextIntArray = () => o.next().split(" ").map(el => parseInt(el))
const nextCharArray = () => o.next().split("")
const hasNext = () => o.hasNext()
const myout = (...x) => console.log(...x)
const Main = () => {
    const [k,x] = nextIntArray()
    let ans = []
    for(let i = -k+1; i<k; i++){
        ans.push(x+i)
    }
    console.log(ans.join(" "))
}
Main()


Measured memory_bytes: 29812
#include <iostream>
#include <stdio.h>
#include <string.h>
#define int long long

using namespace std;

int a,b,c,x,y,ans=0;

signed main()
{
	scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&x,&y);
	if(c*2<a+b)
	{
		int t=min(x,y);
		ans+=t*c*2;
		x-=t,y-=t;
		if(x)
		{
			if(c*2<a) ans+=c*2*x;
			else ans+=a*x;
		}
		else if(y)
		{
			if(c*2<b) ans+=c*2*y;
			else ans+=b*y;
		}
	}
	else ans=a*x+b*y;
	printf("%lld\n",ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <climits>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <unordered_map>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <random>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

#define INF (int)1e8
#define _INF (int)-1e8
#define INFLL (long long)1e15
#define _INFLL (long long)-1e15
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> P;

/*******************************************************/


typedef ll seg_t;

class SegTree {
private:
	int n;
	vector<seg_t> segtree;
	seg_t exc;
	seg_t (*build_rule)(seg_t, seg_t);
	seg_t build_seg(int k) {
		int l = k * 2 + 1, r = k * 2 + 2;
		return build_rule(segtree[l], segtree[r]);
	}
	seg_t find_rule(int s, int t, int l, int r, int k) {
		if (s == l&&t == r) return segtree[k];
		else {
			int mid = (l + r) / 2;
			if (s < mid&&mid < t) {
				seg_t result1 = find_rule(s, mid, l, mid, k * 2 + 1);
				seg_t result2 = find_rule(mid, t, mid, r, k * 2 + 2);
				return build_rule(result1, result2);
			}
			else if (s < mid) {
				return find_rule(s, t, l, mid, k * 2 + 1);
			}
			else if (mid < t) {
				return find_rule(s, t, mid, r, k * 2 + 2);
			}
		}
	}
public:
	SegTree(vector<seg_t> a, seg_t init, seg_t (*f)(seg_t, seg_t)) {
		n = (ll)pow(2, ceil(log2(a.size())));
		segtree = vector<seg_t>(n * 2 - 1, init);
		exc = init;
		build_rule = f;
		Loop(i, a.size()) segtree[n - 1 + i] = a[i];
		Loopr(i, n - 1) segtree[i] = build_seg(i);
	}
	void update(int k, seg_t x, bool add_flag = false) {
		k += n - 1;
		segtree[k] = add_flag ? segtree[k] + x : x;
		while (k > 0) {
			k = (k - 1) / 2;
			segtree[k] = build_seg(k);
		}
	}
	// note: range is [s, t)
	seg_t search(int s, int t) {
		if (s == t) return exc;
		return find_rule(s, t, 0, n, 0);
	}
};

seg_t seg_build_rule(seg_t a, seg_t b) {
	return a + b;
}

int main() {
	int n; cin >> n;
	int q; cin >> q;
	vector<seg_t> a(n, 0);
	SegTree segtree(a, 0, seg_build_rule);
	Loop(i, q) {
		int c, x, y; cin >> c >> x >> y;
		if (c == 0) {
			segtree.update(x - 1, y, true);
		}
		else {
			cout << segtree.search(x - 1, y) << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 6768
N,M = (int(i) for i in input().split())
e = [tuple([int(i) for i in input().split()]) for i in range(M)]
d = {}
for k,v in e:
    if k in d.keys():  d[k].append(v)
    else:   d[k] = [v]
ans_dict = {}
for k,v in d.items():
    v.sort()
    r = str(k).zfill(6)
    for i in range(len(v)):
        ans_dict[(k,v[i])] = r+str(i+1).zfill(6)
for ans in e:
    print(ans_dict[ans])


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

int main(){
  ll ans = 0;

  string x;
  cin >> x;

  for(int i = 0; i < (1 << x.size()-1); i++){
    ll tmp_sum = 0;
  	bitset<10> bit(i);
    rep(j, x.size()-1){
      if(bit.test(j)){
        ans += (int)(x[j]-'0') + tmp_sum * 10;
        tmp_sum = 0;
      } else {
        tmp_sum *= 10;
        tmp_sum += (int)(x[j]-'0');
      }  
    }
    ans += (int)(x[x.size()-1]-'0') + tmp_sum * 10;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <math.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define drep(i,n) for (int i = n; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

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


//------------------------------------------------------------
int main() {
  string s, t;
  bool bl=false;
  cin >> s >> t;

  sort(all(s)); sort(t.rbegin(), t.rend());

  if (s.size()<t.size())
  {
    rep(i, s.size()) if ((s.at(i)<t.at(i)) || (i+1==s.size()&&s.at(i)==t.at(i))) bl=true;
  }
  else
  {
    rep(i, t.size()) if (s.at(i)<t.at(i)) bl=true;
  }

  if (bl) cout << "Yes";
  else    cout << "No";
  cout << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n,m,u,v,cnt,head[N],to[N*2],nxt[N*2];
void adde(int u,int v){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
namespace ring{
	int fu,fv,dis;
	bool flag,vis[N];
	void dfs1(int pre,int u){
		if(flag){
			return;
		}
		vis[u]=true;
		int v;
		for(int i=head[u];i;i=nxt[i]){
			v=to[i];
			if(v!=pre){
				if(vis[v]){
					fu=u;
					fv=v;
					flag=true;
					return;
				}else{
					dfs1(u,v);
				}
			}
		}
	}
	void dfs2(int pre,int u,int dep){
		if(flag){
			return;
		}
		if(u==fv){
			dis=dep;
			flag=true;
			return;
		}
		int v;
		for(int i=head[u];i;i=nxt[i]){
			v=to[i];
			if(v!=pre){
				if((u==fu&&v==fv)||(v==fu&&u==fv)){
					continue;
				}else{
					dfs2(u,v,dep+1);
				}
			}
		}
	}
	int calc(){
		dfs1(0,1);
		flag=false;
		dfs2(0,fu,0);
		return dis+1;
	}
}
namespace solve1{
	int sum[N];
	void dfs(int pre,int u){
		int v;
		for(int i=head[u];i;i=nxt[i]){
			v=to[i];
			if(v!=pre){
				sum[v]=-sum[u];
				dfs(u,v);
			}
		}
		for(int i=head[u];i;i=nxt[i]){
			v=to[i];
			if(v!=pre){
				sum[u]+=sum[v];
			}
		}
	}
	void solve(){
		sum[1]=1;
		dfs(0,1);
		if(sum[1]){
			puts("-1");
		}else{
			int ans=0;
			for(int i=1;i<=n;i++){
				ans+=abs(sum[i]);
			}
			printf("%d\n",ans);
		}
	}
}
namespace solve2{
	int fu,fv,fa[N],sum[N];
	void dfs(int pre,int u){
		int v;
		for(int i=head[u];i;i=nxt[i]){
			v=to[i];
			if(v!=pre){
				if((u==fu&&v==fv)||(v==fu&&u==fv)){
					continue;
				}else{
					fa[v]=u;
					sum[v]=-sum[u];
					dfs(u,v);
				}
			}
		}
		for(int i=head[u];i;i=nxt[i]){
			v=to[i];
			if(v!=pre){
				if((u==fu&&v==fv)||(v==fu&&u==fv)){
					continue;
				}else{
					sum[u]+=sum[v];
				}
			}
		}
	}
	void solve(){
		fu=ring::fu;
		fv=ring::fv;
		sum[fu]=1;
		dfs(0,fu);
		if(sum[fu]&1){
			puts("-1");
		}else{
			int delta=-sum[fu]/2,ans=abs(delta);
			for(int i=fv;i;i=fa[i]){
				sum[i]+=delta;
			}
			sum[fu]+=delta;
			for(int i=1;i<=n;i++){
				ans+=abs(sum[i]);
			}
			printf("%d\n",ans);
		}
	}
}
namespace solve3{
	int fu,fv,ans,fa[N],sum[N],f[N],a[N];
	void dfs(int pre,int u){
		int v;
		for(int i=head[u];i;i=nxt[i]){
			v=to[i];
			if(v!=pre){
				if((u==fu&&v==fv)||(v==fu&&u==fv)){
					continue;
				}else{
					fa[v]=u;
					sum[v]=-sum[u];
					dfs(u,v);
				}
			}
		}
		for(int i=head[u];i;i=nxt[i]){
			v=to[i];
			if(v!=pre){
				if((u==fu&&v==fv)||(v==fu&&u==fv)){
					continue;
				}else{
					sum[u]+=sum[v];
					f[u]+=f[v];
				}
			}
		}
		if(f[u]==0){
			ans+=abs(sum[u]);
		}else{
			a[++a[0]]=f[u]==1?-sum[u]:sum[u];
		}
	}
	void solve(){
		fu=ring::fu;
		fv=ring::fv;
		sum[fu]=1;
		f[fu]++;
		f[fv]--;
		dfs(0,fu);
		if(sum[fu]){
			puts("-1");
		}else{
			sort(a+1,a+a[0]+1);
			int mid=(a[0]+1)/2;
			ans+=abs(a[mid]);
			for(int i=1;i<=a[0];i++){
				ans+=abs(a[i]-a[mid]);
			}
			printf("%d\n",ans);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		adde(u,v);
		adde(v,u);
	}
	if(m==n-1){
		solve1::solve();
	}else if(ring::calc()&1){
		solve2::solve();
	}else{
		solve3::solve();
	}
	return 0;
}

Measured memory_bytes: 9216
import java.util.*;


class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int K = sc.nextInt();
        sc.nextLine();

        int[] list = new int[N];
        double max = 0;
        double tmp = 0;

        for (int i = 0; i < N; i++) {
            list[i] = sc.nextInt();
            tmp += pre(list[i]);
            if (i == K-1) {max = tmp;}
            if (i >= K) {
                tmp -= pre(list[i-K]);
                max = Math.max(max, tmp);
            }
        }
        System.out.println(max);
    }

    static double pre (int x) {
        return ((double)x + 1) / 2;
    }
}

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

int d,g,p[11],c[11],ans=1e9;

int main(){
	cin>>d>>g;
	for(int i=0;i<d;++i){
		cin>>p[i]>>c[i];
	}

	for(int bit=0;bit<(1<<d);++bit){
		int temp=0;
		int point=0;
		int  rest_max=-1;
		for(int i=0;i<d;++i){
			if(bit&(1<<i)){
				temp+=p[i];
				point+=((i+1)*100)*p[i]+c[i];
			}else{
				rest_max = i;
			}
		}
		if(point<g){
			int point1=100*(rest_max+1);
			int need=(g-point+point1-1)/point1;
			if(need>=p[rest_max]){
				continue;
			}
			temp+=need;
		}
		ans=min(ans,temp);
	}
	cout<<ans<<endl;

}

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

#define  __  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  int  long long
#define  endl  '\n'
const double pi = acos(-1);
const int mod = 1e9 + 7;
//______________________


const int N = 2e5+5;
vector<int> g[N];
int sub[N], ans[N];

void dfs(int v, int par, int add)
{
   add += sub[v];
   ans[v] += add;
   
   for(int u: g[v])
   {
      if(u == par) continue;
      dfs(u, v, add);
   }
}

int32_t main()
{ 
 
  
  int n, q;

  cin >> n >> q;

  for(int i = 1; i < n; i++)
  {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }

  for(int i = 1; i <= q; i++)
  {
    int p, x;
    cin >> p >> x;
    sub[p] += x;
  }

  dfs(1, 0, 0);

  for(int i = 1; i <= n; i++)
    cout << ans[i] << ' ';

 return 0;
}

Measured memory_bytes: 25600
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;

int a, b, t;

int main()
{
    scanf("%d%d%d",&a,&b,&t);
    int ans = 0;
    int k = a;
    while(t >= k){
      ans += b;
      k += a;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int N;
	while(cin>>N){
		if(N==0){
			break;
		}
		int c,cnt=0;
		for(int i=1;i<N;i++){
			c=i;
			int cn=i+1;
			while(c<N){
				c+=cn;
				cn++;
			}
			if(c==N)cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int W, H, N; cin >> W >> H >> N;
  vector<int> x(N), y(N), a(N); REP(i, N) cin >> x[i] >> y[i] >> a[i];
  vector<int> widvec(W); REP(i, W) widvec[i] = 0;
  vector<int> heivec(H); REP(i, H) heivec[i] = 0;
  REP(i, N) {
    if(a[i] == 1) for(int k = 0; k < x[i]; ++k) widvec[k] = 1;
    if(a[i] == 2) for(int k = x[i]; k < W; ++k) widvec[k] = 1;
    if(a[i] == 3) for(int k = 0; k < y[i]; ++k) heivec[k] = 1;
    if(a[i] == 4) for(int k = y[i]; k < H; ++k) heivec[k] = 1;
  }
  int wid = 0;
  int hei = 0;
  for(int i = 0; i < W; ++i) if(widvec[i] == 0) wid++;
  for(int i = 0; i < H; ++i) if(heivec[i] == 0) hei++;
  cout << wid * hei << endl;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, A, B = map(int, rl().split())
    X = list(map(int, rl().split()))
    
    ans = 0
    for i in range(N - 1):
        ans += min((X[i + 1] - X[i]) * A, B)
    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 14168
h, w = map(int, input().split())
grid = [str(input()) for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            continue
        if i >= 1:
            dp[i][j] += dp[i - 1][j]
        if j >= 1:
            dp[i][j] += dp[i][j - 1]
        dp[i][j] %= mod
print(dp[-1][-1])

Measured memory_bytes: 44612
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <string>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define LL long long
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int MOD=1e9+7;
//
int main(){
  int A,B,C,D;
  cin>>A>>B>>C>>D;
  cout<<min(A,B)+min(C,D)<<endl;
  return 0;
}


Measured memory_bytes: 256