akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>

using namespace std;

class Piece;

// ツマツッツプツ湘ョツ陛ア
char map[10][60];
Piece *pmap[10][60];

int width;
int height;


class Piece {

public:

  // ツコツδ督スツトツδ可クツタ
  Piece(int x, int y) {
    m = 0;
    mx = 0;
    parent=NULL;
    helper(x, y, map[x][y]);
    xl = 100;
    xr = 0;
  }

  // ツ重ツ心
  int m;
  double mx;

  int rm;
  double rmx;

  // ツ支ツつヲツ点
  int xl;
  int xr;

  // ツ篠ゥツ閉ェツづ個親
  Piece *parent;
  vector<Piece*> children;

  bool check() {
    //cout << m << ' ' << mx << '\n';
    //cout << xl << ' ' << xr << "@\n";
    rm = m;
    rmx = m*mx;
    for(int i=0; i<children.size(); i++) {
      if(children[i]->check()==false) return false;
      rmx += children[i]->rm*children[i]->rmx;
      rm += children[i]->rm;
    }
    rmx /= rm;
    return xl < rmx && rmx < xr;
  }

private:
  
  void helper(int x, int y, char c) {

    if(map[x][y]!=c) return;
    map[x][y] = '.';
    pmap[x][y] = this;

    if(x>0) helper(x-1, y, c);
    if(x<width-1) helper(x+1, y, c);
    if(y>0) helper(x, y-1, c);
    if(y<height-1) helper(x, y+1, c);

    mx = (m*mx + x+0.5) / (double)(m+1);
    m++;
  }
};

int main() {

  

  while(1) {

    vector<Piece*> l;
    Piece *root;

    l.clear();

    cin >> width;
    cin >> height;

    if(width==0 && height==0) break;
    
    // ツ渉可甘コツ可サ
    for(int j=0; j<height; j++) {
      for(int i=0; i<width; i++) {
	cin>>map[i][j];
	pmap[i][j]=NULL;
      }
    }

    // ツコツδ督スツトツδ可クツト
    for(int i=0; i<width; i++) {
      for(int j=0; j<height; j++) {
	if(map[i][j]!='.') {
	  l.push_back(new Piece(i, j));
	}
      }
    }

    // ツ親ツ子ツ甘鳴係ツ津ィツ義
    for(int j=0; j<height; j++) {
      for(int i=0; i<width; i++) {
	//cout << (pmap[i][j]==NULL?'.':'*');
	if(j!=height-1) {
	  if(pmap[i][j]!=NULL && pmap[i][j+1]!=NULL && pmap[i][j]!=pmap[i][j+1]) {
	    if(pmap[i][j]->parent==NULL) {
	      pmap[i][j]->parent = pmap[i][j+1];
	      pmap[i][j+1]->children.push_back(pmap[i][j]);
	    }
	    if(i<pmap[i][j]->xl) pmap[i][j]->xl = i;
	    if(pmap[i][j]->xr<i+1) pmap[i][j]->xr = i+1;
	  }
	} else {
	  // ツ暗ェツ氾板可コ
	  if(pmap[i][j]!=NULL) {
	    //cout << "|";
	    if(i<pmap[i][j]->xl) pmap[i][j]->xl = i;
	    if(pmap[i][j]->xr<i+1) pmap[i][j]->xr = i+1;
	    root = pmap[i][j];
	  }
	}
      }
      //cout << "\n";
    }

    // ツ重ツ心ツ板サツ津ィ
    cout << (root->check() ? "STABLE" : "UNSTABLE") << "\n";
  }
  
  
}

Measured memory_bytes: 0
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] str = Console.ReadLine().Split(' ');
            int[] l = new int[n];
            for(int i = 0;i<n;i++)
            {
                l[i] = int.Parse(str[i]);
            }
            Array.Sort(l);
            int count = 0;
            for(int i = 0;i<n;i++)
            {
                for(int j = 0;j<n;j++)
                {
                    for(int k = 0;k<n;k++)
                    {
                        if(i<j && j<k)
                        {
                            if(l[i]==l[j]){continue;}
                            if(l[i]==l[k]){continue;}
                            if(l[j]==l[k]){continue;}
                            if((l[i]+l[j])<=l[k]){continue;}
                            count++;
                        }
                    }
                }
            }
            Console.WriteLine(count);
        }
    }
    
}

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

int main(void){
  int N;
  cin >> N;
  int first[N];
  int second[N];
  for(int i=0;i<N;i++){
    cin >> first[i] >> second[i];
    }
  int count = 0;
  for(int i=0;i<N-2;i++){
    int c = 0;
    for(int j=0;j<3;j++){
      if(first[i+j] == second[i+j]){
        c += 1;
      }
    }
    count = (c >= count) ? c : count;
  }
  
  if (count >= 3){
    cout << "Yes" << endl;
  }else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//(a+b-1)/b

signed main(){
	int n; cin>>n;
	vi a(n);
	rep(i,0,n)cin>>a[i];
	vi b=a;
	sort(all(b));
	rep(i,0,n){
		if(a[i]==b[n-1])cout<<b[n-2]<<endl;
		else cout<<b[n-1]<<endl;
	}
	
}

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

#define REP(i,j) for(int i = 0; i < j; i++)
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

int main(){
	int p1,q;
	cin >> p1 >> q;
	int t = gcd(p1,q);
	q /= t;
	vector<int> pl;
	pl.push_back(2);
	pl.push_back(3);
	for(int i = 5; i*i < 1e9; i+=2){
		bool f = true;
		for(int j = 3; j*j <= i; j+=2){
			if(i % j == 0)f = false;
		}
		if(f) pl.push_back(i);
	}
	for(int i = 0; i < pl.size(); i++){
		while(q%(pl[i]*pl[i]) == 0){
			q /= pl[i];
		}
	}
	cout << q << endl;
	return 0;
}



Measured memory_bytes: 3184
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define db double 
using namespace std;
int main(){
	db n,m;
	scanf("%lf%lf",&n,&m);
	db ans=0,pp=(pow(2,m)-1)/(pow(2,m));
	for(int i=1;i<=1000;++i)
		ans+=i*pow(pp,i-1)*m*1900*(1-pp)+100*(n-m)*pow(pp,i-1);
	printf("%.0lf",ans);	
	return 0;
}


Measured memory_bytes: 512
from collections import deque
H, W = [int(_) for _ in input().split()]
e = "#" * (W + 2)
maze = [e]
for i in range(H):
    s = input()
    maze.append("#" + s + "#")
maze.append(e)
max_count = 0
for h in range(H):
    for w in range(W):
        visited = [[False for i in range(W+2)] for j in range(H+2)]
        visited[h+1][w+1] = True
        if maze[h+1][w+1] == '#':
            continue
        q = deque([[w+1, h+1, 0]])
        def search(x, y, c):
            if maze[y][x] == '.' and not visited[y][x]:
                q.append([x, y, c+1])
                visited[y][x] = True
        count = 0
        while len(q) != 0:
            p = q.popleft()
            search(p[0]+1, p[1], p[2])
            search(p[0]-1, p[1], p[2])
            search(p[0], p[1]+1, p[2])
            search(p[0], p[1]-1, p[2])
            count = p[2]
        max_count = max(max_count, count)
print(max_count)






Measured memory_bytes: 67824
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1ll<<30;
const ll longINF = 1ll<<60;
const ll MOD = 1000000007;
const bool debug = 0;
//---------------------------------//

vector<int> z_algorithm(string s) {
	vector<int> res(s.size());
	
	res[0] = s.size();
	
	int i = 1, j = 0;
	
	while (i < s.size()) {
		while (i + j < s.size() && s[j] == s[i + j]) j++;
		res[i] = j;
		if (j == 0) { i++; continue; }
		int k = 1;
		while (i + k < s.size() && k + res[k] < j) res[i + k] = res[k], k++;
		i += k;
		j -= k;
	}
	
	return res;
}

int main() {
	int N;
	string S;
	
	cin >> N >> S;
	
	int ans = 0;
	REP(i, N) {
		vector<int> v = z_algorithm(S.substr(i));
		int n = N - i;
		FOR(i, 1, n) {
			chmax(ans, min(v[i], i));
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
    var Arr=input.split("\n");
    var A=Arr[1].split(" ").map(Number);
    var N=Arr[0];
    console.log(A.join(" "));

    let v;
    let j;

    
    for(let i = 1; i < N; i++){
        
        let answer = [];
        
        v = A[i];
        j = i-1;
        
        while( (j>=0) && (A[j] > v)){
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        
        console.log(A.join(" "));
    }


Measured memory_bytes: 16536
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define N 200005
 
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
 	
 	string s,t;
 	cin>>s>>t;
 	int val=1;
 	for(int i=0;i<s.size();i++)
 		if(s[i]!=t[i])
 			val=0;
 	if(val)
 		cout<<"Yes"<<endl;
 	else
 		cout<<"No"<<endl;
 	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> d(n+1);
  d[0] = 0;
  rep(i, n) cin >> d[i+1];

  map<int, int> dict;
  for(auto v : d) {
    dict[v] += 1;
  }

  // d[i]==0, d[i]==12に2人いる場合は0
  if(dict[0] >= 2 || dict[12] >= 2) {
    cout << 0 << endl;
    return 0;
  }
  // d[i]に3人いる場合は0
  for(int i=1;i<=11;i++) {
    if(dict[i] >= 3) {
      cout << 0 << endl;
      return 0;
    }
  }

  // d[i]に2人いる場合は左右に振り分ける
  map<int, int> lr;
  for(int i=1;i<=11;i++) {
    int is = -1;
    if(dict[i] == 2) {
      rep(j, n+1) {
        if(d[j] == i) {
          lr[j] = is;
          is = 1;
        }
      }
    }
  }

  auto d_ij = [](int di, int dj) {
    int mx = max(di, dj);
    int mn = min(di, dj);
    return min(mx-mn, 24-(mx-mn));
  };

  auto get_d = [&](int mask, int i) {
    int di;
    if(d[i] == 0 || d[i] == 12) {
      di = d[i];
    } else if(lr[i] == 0) {
      di = mask & (1 << (d[i]-1)) ? d[i] : 24 - d[i];
    } else {
      di = lr[i] == 1 ? d[i] : 24 - d[i];
    }
    return di;
  };

  int ans = 0;
  for(int mask = 0; mask < (1 << 12); mask++) {
    int v = 100000000;
    rep(i, n+1) {
      rep(j, n+1) {
        if(i == j) continue;
        int di = get_d(mask, i);
        int dj = get_d(mask, j);
        v = min(v, d_ij(di, dj));
      }
    }
    ans = max(ans, v);
  }

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


Measured memory_bytes: 3612
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll>P;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
ll cmp(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n;cin>>n;
    while(!(n/100==n/10%10&&n/10%10==n%100%10))
        n++;
    cout<<n<<endl;
    
    
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------


Measured memory_bytes: 256
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long sum = 0;
    for(int i = 1; i <= N; i++){
    	if(i % 3 == 0 || i % 5 == 0){
    	}else{
    		sum += i;
    	}
    }
    
    System.out.print(sum);
  }
}

Measured memory_bytes: 35876
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;

int main(){
  int x,y,z,K; cin>>x>>y>>z>>K;
  vector<ll> a(x), b(y), c(z);
  rep(i, x) cin >> a[i];
  rep(i, y) cin >> b[i];
  rep(i, z) cin >> c[i];

  sort(all(a), greater<ll>());
  sort(all(b), greater<ll>());
  sort(all(c), greater<ll>());

  vector<ll> ans;
  rep(i, x) rep(j, y){
    if((i+1)*(j+1) > K) continue;
    rep(k, z){
      if((i+1)*(j+1)*(k+1) > K) continue;
      ans.pb(a[i]+b[j]+c[k]);
    }
  }

  sort(all(ans), greater<ll>());

  rep(i, K) std::cout << ans[i] << '\n';
}


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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
ll LCM(ll a, ll b) { return a / GCD(a, b)* b; }

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int dp[101000];

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  int n; cin>>n;
  vi a(n);
  rep(i,n) cin>>a[i];
  dp[0]=0;
  dp[1]=abs(a[0]-a[1]);
  irep(i,2,n){
    dp[i]=min(dp[i-2]+abs(a[i-2]-a[i]), dp[i-1]+abs(a[i-1]-a[i]));
  }
  cout<<dp[n-1]<<endl;
}

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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int A, B;
    cin >> A >> B;
    cout << 100 << " " << 100 << endl;
    vector<vector<char>> g(100);
    REP(i, 50) {
        g[i].resize(100);
        fill(ALL(g[i]), '#');
    }
    FOR(i, 50, 100) {
        g[i].resize(100);
        fill(ALL(g[i]), '.');
    }

    int c = 0;
    for(int i = 0;i < 50;i += 2) {
        for(int j = 0;j < 100 && c < A - 1;j += 2, c++) {
            g[i][j] = '.';
        }
    }

    int d = 0;
    for(int i = 99;50 <= i;i -= 2) {
        for(int j = 0;j < 100 && d < B - 1;j += 2, d++) {
            g[i][j] = '#';
        }
    }
    REP(i, 100) {
        REP(j, 100) {
            cout << g[i][j];
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define print(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
#define yes "Yes"
#define no "No"
using ll = long long;
using namespace std;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int A,B,K;
int main(){
    cin >> A >> B >> K;
    repi(i,A,B) if(i < A + K || i > B - K) print(i);
}

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

int main() {
    int64_t a = 0, b = 0, n = 0;

    cin >> a >> b >> n;

    double ans = 0;
    int64_t first = 0;
    int64_t last  = n;
    int64_t mid   = n / 2;
    ans = floor(a * mid / b) - a * floor(mid / b);
    if (ans <= floor(a * (mid + 1) / b) - a * floor((mid + 1) / b)) {
        first = mid + 1;
    } else {
        last = mid - 1;
    }
    while (first <= last) {
        mid = first + (last - first) / 2;
        double tmp = floor(a * mid / b) - a * floor(mid / b);
        if (tmp >= ans) {
            ans = tmp;
            first = mid + 1;
        } else {
            last = mid - 1;
        }
    }

    cout << ans << endl;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x;
  cin >> x;
  cout << x * x * x << endl;
  return 0;
}


Measured memory_bytes: 3128
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

int main(){
  int n; cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  for(int i = 0; i < n; i++){
    if(!(a[i]%2)){
      if(!(a[i]%3 == 0 || a[i]%5 == 0)){
        cout << "DENIED" << endl;
        return 0;
      }
    }
  }
  cout << "APPROVED" << endl;
}


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


void solve(std::string AtCoder, std::string s, std::string Contest){
    cout << "A" << s[0] << "C" << endl;
}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::string AtCoder;
    std::cin >> AtCoder;
    std::string s;
    std::cin >> s;
    std::string Contest;
    std::cin >> Contest;
    solve(AtCoder, s, Contest);
    return 0;
}


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

using namespace std;

typedef long long int ll;

int main() {
    int n;
    cin>>n;
    ll a[n] , count=0;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n-1;i++)
    {
        if(a[i]>a[i+1]) count+=(a[i]-a[i+1]) , a[i+1]=a[i];
    }
    cout<<count;
}


Measured memory_bytes: 5156
import java.util.*;

public class Main
{
    public static void main(String... args)
    {
        final Scanner lineScanner = new Scanner(System.in);
        final Scanner scanner = new Scanner(lineScanner.nextLine());
        final List<Integer> integers = new ArrayList<Integer>();
        while (scanner.hasNextInt()) {
            integers.add(scanner.nextInt());
        }
        Collections.sort(integers);
        System.out.println(integers.toString().replaceAll("[^0-9]+", " ").trim());
    }
}

Measured memory_bytes: 17176
function Main(input) {
  input = input.split("\n");
  var m = input[0].split(" ");
  var a = parseInt(m[0], 10), b = parseInt(m[1], 10), c = parseInt(m[2], 10);
  console.log(a * b * Math.sin(c * Math.PI / 180) / 2);
  console.log(a + b + Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(c * Math.PI / 180)));
  console.log(b * Math.sin(c * Math.PI / 180));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 15556
if __name__ == "__main__":
    while True:
        h,w = map(int,input().split())
        if w is not 0 or h is not 0:
            for i in range(w):
                print("#",end="")
            print("")
            for i in range(h-2):
                print("#",end="")
                for j in range(w-2):
                    print(".",end="")
                print("#",end="")
                print("")
            for i in range(w):
                print("#",end="")
            print("")   
            print("")
        else:
            break

Measured memory_bytes: 8948
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define md 1000000007
#define ld long double
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n, i = 0, j= 0, k = 0, l = 0, m = 0, a = 0, b = 0, sum = 0, x = 0, y = 0, z = 0, c, p;
    string s;
    cin >> s;
    l = s.length();
    for(i = 0; i < l; i++){
        cout << "x";
    }

    return 0;
}


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

using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int64_t K, N;
	cin >> K >> N;
	vector<int64_t> vec(N);
	vector<int64_t> len(N);
	
	for (int i = 0; i < N ; i++)
	{
		cin >> vec.at(i);
	}
	 int64_t ans= abs(vec.at(0) - 0) + abs(K - vec.at(N - 1));
	 for (int i = 1; i < N; i++)
	 {
		 ans = max(ans, vec.at(i) - vec.at(i - 1));
	 }
	 cout << K-ans << endl;

}


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

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

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

    int ans = 1e9;
    for(int i = 1; i <= 100; i++){
        int cost = 0;
        for(int j = 0; j < n; j++){
            int a = A[j] - i;
            cost += a * a;
        }
        ans = min(ans, cost);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Integer[] a = new Integer[n];
        Arrays.setAll(a, i -> Integer.parseInt(sc.next()));
        sc.close();

        // 主処理
        int sum = Arrays.stream(a).mapToInt(i -> i).sum();
        double ave = (double) sum / n;
        double minDist = Double.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < n; i++) {
            double dist = Math.abs(a[i] - ave);
            if (dist < minDist) {
                minDist = dist;
                index = i;
            }
        }
        int result = index;

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 27092
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b,s;
    int a1,b1;
    cin>>a>>b>>a1>>b1>>s;
    if(s==a)a1--;
    else b1--;
    cout<<a1<<" "<<b1<<endl;
    return 0;
}

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

int main() {
  string N;
  cin >> N;
  if (N.at(0)==N.at(1) && N.at(1)==N.at(2)){
  cout << "Yes" << endl;
  }
  else if (N.at(1)==N.at(2) && N.at(2)==N.at(3)){
  cout << "Yes" << endl;
  }
  else{
  cout << "No" << endl; 
  }
}



Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = [sum(a)]
for i in range(n):
    b.append(b[-1] - a[i])
flag = True
if n == 0:
    if a[0] == 1:
        count = 1
    else:
        count = -1
else:
    if a[0] != 0:
        flag = False
    else:
        count = 1
        temp = 1
        for i in range(1, n + 1):
            temp2 = min(temp * 2, b[i])
            count += temp2
            temp = temp2 - a[i]
            if temp <= 0:
                if i != n:
                    flag = False
                    break
        if temp != 0:
            flag = False
if flag == True:
    print(count)
else:
    print(-1)

Measured memory_bytes: 20156
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
typedef vector<int> vi;
typedef pair<int, int> p;
#define F(x,to) for(int x=0;x<(to);++x)
#define FF(x,from,to) for(int x=(from);x<(to);++x)
#define RF(x,from) for(int x=(from)-1;x>=0;--x)
#define RFF(x,from,to) for(int x=(from)-1;x>=(to);--x)
#define FR(x,arr) for(auto& x:arr)
#define I(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();++x)
#define A(a) (a.begin()),(a.end())
#define R(a) (a.rbegin()),(a.rend())
#define S(x) (int)(x).size()
#define F1(x,val) fill_n(x,sizeof(x)/sizeof(*x),val)
#define F2(x,val) fill_n(*x,sizeof(x)/sizeof(**x),val)
#define F3(x,val) fill_n(**x,sizeof(x)/sizeof(***x),val)
#define F4(x,val) fill_n(***x,sizeof(x)/sizeof(****x),val)
//-------------------------------------------------------

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  string s;
  cin>>s;
  int res=0;
  F(i,S(s)) res+=s[i]-'0';
  cout<<(res%9?"No":"Yes")<<'\n';
}

Measured memory_bytes: 3724
import java.util.*;
public class Main {
	static long count[] = new long[10];
	static long max = 0;
	static long ansCount[] = new long[10];
	static boolean canUse[] = new boolean[10];
	static int need[] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long num = sc.nextInt();
		int type = sc.nextInt();
		for(int i = 0; i < type; i ++) {
			canUse[sc.nextInt()] = true;
		}
		check(2, num);
		for(int i = 9; i > 0; i --) {
			for(int j = 0; j < ansCount[i]; j ++) {
				System.out.print(i);
			}
		}
		System.out.println();
	}
	public static boolean check(int minNeed, long num) {
		if(minNeed >= 8 || minNeed > num) {
			return false;
		}
		int useNumber = 9;
		for(; useNumber > 0; useNumber --) {
			if(need[useNumber] == minNeed && canUse[useNumber]) {
				break;
			}
		}
		if(useNumber == 0) {
			return check(minNeed + 1, num);
		}
		long rest = num % minNeed;
		count[useNumber] = (num - rest) / minNeed;
		if(rest == 0) {
			repl();
			count[useNumber] = 0;
			return true;
		}
		while(count[useNumber] >= 0) {
			if(check(minNeed + 1, rest)) {
				break;
			}
			count[useNumber] --;
			rest += minNeed;
		}
		count[useNumber] = 0;
		return false;
	}

	public static void repl() {
		long sum = 0;
		for(int i = 0; i < 10; i ++) {
			sum += count[i];
		}
		if(sum >= max) {
			boolean replace = false;
			for(int i = 9; i > 0; i --) {
				if(count[i] > ansCount[i]) {
					replace = true;
					break;
				}else if (count[i] < ansCount[i]) {
					replace = false;
					break;
				}
			}
			if(sum > max || replace) {
				max = sum;
				for(int i = 0; i < 10; i ++) {
					ansCount[i] = count[i];
				}
			}
		}
	}
}

Measured memory_bytes: 24400
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int sec = sc.nextInt();
		int time = 0;
		int min = 0;
		while(3600 <= sec){
			time++;
			sec -= 3600;
		}
		while(60 <= sec){
			min++;
			sec -= 60;
		}
		
		System.out.println(time + ":" +  min + ":" + sec);

	
	}
}

Measured memory_bytes: 26372
def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [list(map(int,input().split())) for _ in range(Q)]
    dict = {}

    for i in range(1,10**5+1):
    #for i in range(1,6):
        dict[i] = 0

    for i in range(N):
        dict[A[i]] += 1

    sum = 0
    for i in range(1,10**5+1):
        #for i in range(1,6):
        if dict[i] != 0:
            sum += dict[i]*i

    for i in range(Q):
        sum = sum +(dict[B[i][0]]*B[i][1] - dict[B[i][0]]*B[i][0])

        dict[B[i][1]] += dict[B[i][0]]
        dict[B[i][0]] = 0
        #print(dict)
        print(sum)

main()


Measured memory_bytes: 42448
N, K = map(int, input().split())

# 10^100はでかすぎるので和の第1項(10^100の整数倍、巨大)と第2項(端数)が干渉することはない

#求める場合の数。ありうる和が全部で何通りか
possible = 0

# firstからlastまでの和を速く計算する
def sumRange(first, last):
    count = last - first + 1
    return int((first + last) * count / 2)

# 選んだ数値の個数がselectedのとき
# 第1項の係数はselectedになるので、選んだ個数が違えば和も必ず異なる
# よって、選んだ個数ごとに分けて考えてよい
for selected in range(K, (N + 1) + 1):
    # 最小値は数列のうち先頭selected個をとったもの
    minFraction = sumRange(0, selected - 1)

    # 最大値は数列のうち末尾selected個をとったもの
    maxFraction = sumRange(N - selected + 1, N)

    # 最小値と最大値の間の数は全てありえるので個数は
    possible += maxFraction - minFraction + 1

# modで小さくして答えろとの指示
print(possible % (10 **9 + 7))



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

using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
#define inf 1ll<<60
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
#define int llong
#define be(x) x.begin(), x.end()
typedef pair<int, int> P;


signed main(){
	int n;
	int ans = 0;
	string a, b, c;
	cin >> n >> a >> b >> c;

	for(int i = 0; i < n; i++){
		if(a[i] == b[i] && b[i] == c[i])
			continue;
		else if(a[i] == b[i])
			ans++;
		else if(b[i] == c[i])
			ans++;
		else if(c[i] == a[i])
			ans++;
		else
			ans += 2;
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using gr = vector<vll>;
using wgr = vector<vpll>;

#define pb push_back
#define FOR(i, m, n) for (ll i(m); i < n; i++)
#define REP(i, n) FOR(i, 0, n)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
struct d_ {
    template<typename T> d_ & operator ,(const T & x) { cerr << ' ' <<  x; return *this;}
    template<typename T> d_ & operator ,(const vector<T> & x) { for(auto x: x) cerr << ' ' <<  x; return *this;}
} d_t;
#define dbg(args ...) { d_t,"|",__LINE__,"|",":",args,"\n"; }
#define EPS (1e-10)
#define INF (1LL<<61)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define all(x) begin(x),end(x)
#define IN(n) ll n;cin >> n;
#define x first
#define y second

int main(void) {
    ios_base::sync_with_stdio(false);
    ll a,b; cin >> a >> b;
    if(a+b==15) cout << "+";
    else if(a*b==15) cout << "*";
    else cout << "x";
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import defaultdict

# 切り離す必要があるものを辺として、二部グラフの判定
N,M = map(int,input().split())

# 補グラフ
rng = range(1,N+1)
graph = [None] + [set(x for x in rng if x != y) for y in rng]
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].remove(b)
    graph[b].remove(a)

color = [None] * (1+N)
size = defaultdict(lambda: [0,0])

def set_color(root,x,c):
    size[root][c] += 1
    color[x] = c
    for y in graph[x]:
        if color[y] is None:
            set_color(root,y,1-c)
        elif color[y] == color[x]:
            print(-1)
            exit()

for x in rng:
    if color[x] is None:
        set_color(x,x,0)

# 二部グラフになるべく平均的に分けたい
# 可能なサイズの集合を持つ

se = {0}
for x,y in size.values():
    se = set(s + x for s in se) | set(s + y for s in se)

answer = min(x*(x-1)//2+(N-x)*(N-x-1)//2 for x in se)
print(answer)

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

int main() {
  ll N;
  cin >> N;

  string ans;
  while (N > 0) {
    int c = (N - 1) % 26;
    ans = (char)('a' + c) + ans;
    N = (N - 1) / 26;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int gcd(int a,int b) {
	if (b == 0) return a;
	return gcd(b,a%b);
}

int main() {
	int N;
	cin >> N;
	vector<vector<int>> DP(N, vector<int>(2));
	cin >> DP[0][0];
	DP[0][1] = DP[0][0];
	int other;
	for (int i = 1; i < N; i++) {
		int A;
		cin >> A;
		if (i == 1) other = A;
		else {
			other = gcd(other, A);
		}
		DP[i][0] = gcd(A, DP[i - 1][0]);
		DP[i][1] = max(DP[i - 1][0], gcd(A, DP[i - 1][1]));
	}
	//一番最初をかえる場合を別途考える

	int ans =max( DP[N - 1][1],other);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 5760
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
#from collections import defaultdict
def main():
    n = int(input())
    s = tuple(map(int, tuple(input())))
    num_pos = [] # 各数字がｓ中に最後にあらわれる位置。
    for num in range(10):
        if num in s:
            num_pos.append(n - s[::-1].index(num) - 1)
    unique_num = [0] * n # ｓの各桁でその桁以降にある数字の種類。
    for i1 in range(n):
        unique_num[i1] = sum([np >= i1 for np in num_pos])
    unique_num.append(0)
    r = 0
    for keta1 in range(10):
        if keta1 in s:
            keta1_pos = s.index(keta1)
            for keta2 in range(10):
                if keta2 in s[keta1_pos + 1:]:
                    keta2_pos = s[keta1_pos + 1:].index(keta2) + keta1_pos + 1
                    r += unique_num[keta2_pos + 1]
    print(r)

if __name__ == '__main__':
    main()

Measured memory_bytes: 121760
# D - RGB Triplets

N = int(input())
S = input()
cnt_R = S.count('R')
cnt_G = S.count('G')
cnt_B = S.count('B')
total = cnt_R * cnt_G * cnt_B

expt = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j + (j - i)
        if k < N and (S[i] != S[j] and S[j] != S[k] and S[i] != S[k]):
            expt += 1

print(total - expt)


Measured memory_bytes: 9188
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<int64_t,int64_t> pll;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) begin(a),end(a)
#define sz(s) (s).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

 
void solve()
{
    int a,b,c;cin>>a>>b>>c;
    a-=b;
    if(c>a)cout<<c-a<<endl;
    else cout<<0<<endl;
}

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

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
ll a[maxn],b[maxn];
vector <int>v[maxn];
void f(int n)
{

    for(int i=0; i<v[n].size(); i++)
    {
        int k=v[n][i];
        a[k]+=(b[n]+b[k]);
        b[k]+=b[n];
        for(int i=0;i<v[k].size();i++)
        {
            int l=v[k][i];
            a[l]+=(b[l]+b[k]);
            b[l]+=b[k];
            f(l);
        }

    }
}
int main()
{
    int n,q;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    scanf("%d %d",&n,&q);
    for(int i=0; i<n-1; i++)
    {
        int from,to;
        scanf("%d %d",&from,&to);
        v[from].push_back(to);
    }
    for(int i=0;i<q;i++)
    {
        int w,l;
        scanf("%d %d",&w,&l);
        b[w]+=l;
    }
    a[1]=b[1];
    f(1);
    printf("%lld",a[1]);
    for(int i=2;i<=n;i++)
        printf(" %lld",a[i]);
    return 0;
}


Measured memory_bytes: 24320
A,B,C,D,E,F = map(int,input().split())
water = set()
for i in range(0,F+1,100*A):
    for j in range(0,F+1,100*B):
        if i + j <= F:
            water.add(i + j)
water = list(water)
water.sort()
sugar = set()
for i in range(0,F+1,C):
    for j in range(0,F+1,D):
        if i + j <= F:
            sugar.add(i + j)
sugar = list(sugar)
sugar.sort()
#print(water)
#print(sugar)
ans = [[0,100*A,0]]
for i in water:
    for j in sugar:
        if i == 0 or j == 0:
            continue
        if i + j <= F and (i//100)*E >= j:
            #print(i,j)
            ans.append([(100*j)/(i+j),i+j,j])
ans.sort()
#print(ans)
print(ans[-1][1],ans[-1][2])


Measured memory_bytes: 73480
#include <stdio.h>

int main(){
    int m[201], n, cnt=0, i, flag=1;
    
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &m[i]);
        if(m[i]%2==1) {
            flag=0;
            break;
        }
    }
    
    while(flag){
        for(i=1; i<=n; i++){
            if(m[i]%2==0){
                m[i] = m[i] / 2;
            }
            else{
                flag=0;
                break;
            }
        }
        if(flag==1) cnt++;
    }
    
    printf("%d", cnt);
    return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)

typedef long long ll;

int nNode, nEdge;
// 複数回両替はしないので、sから両替する都市まで円で行き、そこからtまでスヌークで行く。

struct E {
  int a, b, y, s;
};

vector<E> g[100000+10];
ll distY[100000+10];
ll distS[100000+10];
int visited[100000+10];
int counter;
ll ans[100000+10];

struct K {
  int u;
  ll c;
};

bool operator>(const K& a, const K& b) {
  return a.c > b.c;
}

void go(int start, bool useY) {
  ++counter;
  priority_queue<K, vector<K>, greater<K> > q;
  ll* dist = useY ? distY : distS;
  REP(i, nNode+5) {
    dist[i] = 100000000000000000LL;
  }
  q.push((K){start, 0});
  dist[start] = 0;
  while(!q.empty()) {
    K cur = q.top(); q.pop();
    int u = cur.u;
    if(visited[u] == counter) {
      continue;
    }
    // cerr << "> " << u << endl;
    visited[u] = counter;
    REP(i, g[u].size()) {
      E e = g[u][i];
      int v = e.b;
      // cerr << ">> " << v << endl;
      ll c = cur.c + (useY ? e.y : e.s);
      if(visited[v] == counter || c >= dist[v]) {
        continue;
      }
      q.push((K){v, c});
      dist[v] = c;
    }
  }
}

int main(void) {
  int s, t;
  scanf("%d%d%d%d", &nNode, &nEdge, &s, &t);
  REP(iEdge, nEdge) {
    E e;
    scanf("%d%d%d%d", &e.a, &e.b, &e.y, &e.s);
    g[e.a].push_back(e);
    swap(e.a, e.b);
    g[e.a].push_back(e);
    // cerr << e.a << " " << e.b << " " << e.y << " " << e.s << endl;
  }
  go(s, true);
  go(t, false);
  ans[nNode] = 10000000000000000LL;
  // REP(i, nNode+1) {
  //   cerr << distY[i] << " " ;
  // }
  // cerr << endl;
  // REP(i, nNode+1) {
  //   cerr << distS[i] << " " ;
  // }
  // cerr << endl;
  
  for(int i = nNode; i >= 1; --i) {
    ll c = distY[i]+distS[i];
    // cerr << i << " " << c << endl;
    ans[i-1] = min(ans[i], c);
  }
  REP(i, nNode) {
    printf("%lld\n", 1000000000000000LL - ans[i]);
  }
  
  return 0;
}


Measured memory_bytes: 12160
# -*- coding: utf-8 -*-
def linear_search(value, target_list):
    for key in target_list:
        if value == key:
            return True
    return False


def main():
    s_length = raw_input()
    s = raw_input().strip().split(' ')
    t_length = raw_input()
    t = raw_input().strip().split(' ')


    counter = 0
    for t_value in t:
        counter += int(linear_search(t_value, s))

    print counter

if __name__ == '__main__':
    main()

Measured memory_bytes: 6468
#include <algorithm>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <istream>
#include <map>
#include <numeric>
#include <ostream>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>


using namespace std;

typedef long long ll;


class Solution {
 public:
  void solve(std::istream& in, std::ostream& out) {
    ll n, x;
    in >> n >> x;
    ll dp[51][2];
    dp[0][0] = dp[0][1] = 1;
    for (int ctr1 = 1; ctr1 < 51; ++ctr1) {
      dp[ctr1][0] = 1 + 2 * dp[ctr1 - 1][0];
      dp[ctr1][1] = 3 + 2 * dp[ctr1 - 1][1];
    }
    ll rez = 0;
    for (int ctr1 = n; ctr1 >= 0; --ctr1) {
      if (x == dp[ctr1][1]) {
        rez += dp[ctr1][0];
        x = 0;
      } else if (x > dp[ctr1][1] / 2) {
        rez += 1 + (ctr1 > 0 ? dp[ctr1 - 1][0] : 0);
        x -= 1 + dp[ctr1][1] / 2;
      } else {
        --x;
      }
    }
    out << rez;
  }
};

void solve(std::istream& in, std::ostream& out)
{
  out << std::setprecision(12);
  Solution solution;
  solution.solve(in, out);
}
// Powered by caide (code generator, tester, and library code inliner)


#include <fstream>
#include <iostream>


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


  istream& in = cin;


  ostream& out = cout;

  solve(in, out);
  return 0;
}



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

class Program
{
    static void Main()
    {
        var ABCXY = ReadLine().Split().Select(int.Parse).ToArray();
        var A = ABCXY[0];
        var B = ABCXY[1];
        var C = ABCXY[2];
        var X = ABCXY[3];
        var Y = ABCXY[4];

        var c = new List<int>();
        c.Add(A * X + B * Y);
       if(X>Y) c.Add(A * (X - Y) + 2 * C * Y);
        else c.Add(2 * C * X + B * (Y - X));
        c.Add(2 * C * Math.Max(X,Y));
        WriteLine(c.Min());
    }
}

Measured memory_bytes: 13396
h,w = map(int,input().split())
ans = 10**18
if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()
if h > 3:
    maxs = (h//3+1)*w
    mins = (h//3)*w
    ans = min(maxs-mins,ans)
if w > 3:
    maxs = (w//3+1)*h
    mins = (w//3)*h
    ans = min(ans,maxs-mins)
for i in range(1,h):
    a = i*w
    b = (h-i)*(w//2)
    c = (h-i)*(w-(w//2))
    maxs = max(max(a,b),c)
    mins = min(min(a,b),c)
    ans = min(ans,maxs-mins)
for i in range(1,w):
    a = i*h
    b = (w-i)*(h//2)
    c = (w-i)*(h-(h//2))
    maxs = max(max(a,b),c)
    mins = min(min(a,b),c)
    ans = min(ans,maxs-mins)
print(ans)

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

int v[105];

int n;

int sq(int x)
{
	return x*x;
}

int cost_trasformation(int x)
{
	int sum = 0;
	for(int i = 0 ; i < n ; i++)
	{
		sum += sq(v[i] - x);
	}
	return sum;
}

int main()
{
	scanf("%d",&n);
	for(int i = 0; i < n ; i++)
	{
		scanf("%d",&v[i]);
	}
	
	int ans = INT_MAX;
	for(int x = -100; x <= 100; x++)
	{
		ans = min(ans,cost_trasformation(x));
	}

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

	return 0;
}


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

int main() {
    int H, A;
    cin >> H >> A;
    int ans = 0;
    ans = (H + A - 1)/ A;
    cout << ans << endl;
}


Measured memory_bytes: 256
n = int(input())
l = list(map(int,input().split()))

l.sort()
N = l[-1]
if N%2:
    M_L = N//2
    M_R = N//2+1
else:
    M_L = N//2
    M_R = N//2
max_idx = 0
min_dis = N+1

for i in range(n-1):
    if min(abs(l[i]-M_L),abs(l[i]-M_R)) < min_dis:
        max_idx = i
        min_dis = min(abs(l[i]-M_L),abs(l[i]-M_R))
print(str(N)+" "+str(l[max_idx])) 


Measured memory_bytes: 14060
#include <bits/stdc++.h>
using namespace std;
int n, c;
pair<int, int> a[100020];
int v[32][100020];
multiset<int> s;
int main() {
	scanf("%d%d", &n, &c);
	for (int i = 0; i < n; i++) {
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		for (int i = x; i < y; i++) {
			v[c][i] = 1;
		}
	}
	n = 0;
	for (int i = 1; i <= c; i++) {
		pair<int, int> u;
		for (int j = 1; j <= 100000 + 1; j++) {
			if (v[i][j] == 1 && v[i][j - 1] == 0) {
				u.first = j;
			}
			if (v[i][j] == 0 && v[i][j - 1] == 1) {
				u.second = j;
				a[n++] = u;
			}
		}
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		if (s.size() == 0 || a[i].first <= *s.begin()) {
			s.insert(a[i].second);
		} else {
			s.erase(s.begin());
			s.insert(a[i].second);
		}
	}
	printf("%d\n", (int)s.size());
	return 0;
}

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

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	double n;
	cin >> n;
	if(int(n)%2 == 0)	cout << double((n/2)/n) << '\n';
	else cout << double((ceil(n/2))/n) << '\n';	
	return 0;
}

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


const int maxn = 400 + 1;

double dp[maxn][maxn][maxn];

const double eps = 1e-12;

double go(int a, int b, int c, int n)
{
	if (a + b + c > n)
	{
		return 0;
	}

	if (a < 0 || b < 0 || c < 0)
	{
		return 0;
	}

	if (a == 0 && b == 0 && c == 0)
	{
		return 0;
	}

	if (fabs(dp[a][b][c] + 1) > eps)
	{
		return dp[a][b][c];
	}

	dp[a][b][c] = (a * go(a - 1, b, c, n) / n + b * go(a + 1, b - 1, c, n) / n + c * go(a, b + 1, c - 1, n) / n + 1) * n / (1.0 * a + b + c);
	
	return dp[a][b][c];
}

void solve()
{
	for (int i = 0; i < maxn; i++)
	{
		for (int k = 0; k < maxn; k++)
		{
			for (int j = 0; j < maxn; j++)
			{
				dp[i][k][j] = -1;
			}
		}
	}

	int n;
	cin >> n;

	int a = 0, b = 0, c = 0;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		a += (x == 1);
		b += (x == 2);
		c += (x == 3);
	}

	cout << fixed << setprecision(12) << go(a, b, c, n);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("file.in", "r", stdin);//freopen("file.out", "w", stdout);

	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 504064
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

signed main(){

	lli n,q;
	cin>>n>>q;
	string s;
	cin>>s;

	vector<char> t(q),d(q);
	REP(i,0,q)cin>>t[i]>>d[i];

	/*左から落ちる人と右から落ちる人の動きを再現させる。*/
	/*この時左から落ちる人は一番どこにいうるか？*/

	lli left=0;
	lli right=n-1;

	/*leftを動かす*/
	for(lli i=q-1;i>=0;i--){
		if(left>=n)break;
		char nowPos = s[left];
		if(t[i]==nowPos && d[i] == 'L')left++;
		if(left>0 && s[left-1] == t[i] && d[i] =='R')left--;
	}

	for(lli i=q-1;i>=0;i--){
		if(right<0)break;
		char nowPos = s[right];
		if(t[i]==nowPos && d[i] == 'R')right--;
		if(right<n-1 && s[right+1] == t[i] && d[i] == 'L')right++;
	}
	if(DEBUG)cout<<"left="<<left<<" right="<<right<<endl;
	cout<<max(0LL,right - left +1)<<endl;

	return 0;
}

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

int main(void) {
    int X,Y;cin>>X>>Y;
    /*
    2*TURU + 4*KAME = 100;
    2*TURU + 2*KAME = 4;
    2*KAME = 2*KAME = 100 - 4 = 96;
    KAME = 48;
    2*TURU = Y - 4 * KAME >= 0
    KAME = (Y - 2 * X) / 2 = Y - 2 * (Y - 2 * X) = - Y + 4 * X 
    TURU = X - 
    */
    if (Y - 2 * X >= 0 && - Y + 4 * X >= 0 && (Y - 2 * X) % 2 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3120