akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,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;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
template<class T,class Y>T LCM(T a,Y b){return (a*b)/GCD(a,b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

using vi=vector<int>;
using vii=vector<vi>;

#define REP(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()
#define decimal(x) fixed<<setprecision(x)

int main(){
    int n;
    cin>>n;
    rep(i,10){
        if(n<=(i+1)*1000){
            cout<<(i+1)*1000-n<<endl;
            break;
        }
    }
    return 0;
}

//a=97,z=122

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <utility>

typedef long long ll;

using namespace std;

vector<vector<pair<int, ll> > > G(100010);
vector<int> color(100010, -1);

void dfs(int v, int c) {
    color[v] = c;
    for (int i = 0; i < G[v].size(); i++) {
        
        if (color[G[v][i].first] != -1)
            continue;
        else if (G[v][i].second % 2 == 0)
            dfs(G[v][i].first, c);
        else 
            dfs(G[v][i].first, (c+1)%2);
    }
}

int main() {
    int n;  cin >> n;
    int u, v;
    ll w;
    for (int i = 0; i < n-1; i++) {
        cin >> u >> v >> w;
        pair<int, ll> a;
        a.first = u-1;
        a.second = w;
        G[v-1].push_back(a);
        a.first = v-1;
        G[u-1].push_back(a);
        
    }
    

    for (int i = 0; i < n; i++) {
        if (color[i] == -1)
            dfs(i, 0);
    }

    for (int i = 0; i < n; i++)
        cout << color[i] << endl;

    return 0;
}

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

void fnInput(int &a_riElementCnt, vector<int> &a_rviElement, 
             int &a_riTargetCnt , vector<int> &a_rviTarget )
{
  cin >> a_riElementCnt;

  a_rviElement.resize(a_riElementCnt);
  for (int i = 0; i < a_riElementCnt; i++)
    cin >> a_rviElement[i];

  cin >> a_riTargetCnt;

  a_rviTarget.resize(a_riTargetCnt);
  for (int i = 0; i < a_riTargetCnt; i++)
    cin >> a_rviTarget[i];
}

int fnRcsSearch(int a_iPos, const vector<int> &a_cnrviElement, int a_iTarget,
                vector<vector<int>> &a_rvviOK)
{
  if (a_iPos == a_cnrviElement.size())  return 0;
  if (!a_iTarget)    return 1;
  if (a_iTarget < 0) return 0;
  if (a_rvviOK[a_iPos][a_iTarget] != -1)
    return a_rvviOK[a_iPos][a_iTarget];

  a_iPos++; 
  int iRtn0 = fnRcsSearch(a_iPos, a_cnrviElement, a_iTarget, a_rvviOK);
  a_rvviOK[a_iPos][a_iTarget] = iRtn0;
  if (iRtn0)  return iRtn0;

  int iSmallTarget = a_iTarget - a_cnrviElement[a_iPos];
  int iRtn1 = fnRcsSearch(a_iPos, a_cnrviElement, iSmallTarget, a_rvviOK);
  if (iSmallTarget >= 0)
  {
    a_rvviOK[a_iPos][iSmallTarget] = iRtn1;
    return iRtn1;
  }
}

void fnExhSearch(const vector<int> &a_cnrviElement, const vector<int> &a_cnrviTarget)
{
  vector<vector<int>> vviOK(21, vector<int>(2001, -1));
  
  for (int i = 0; i < a_cnrviTarget.size(); i++)
  {
    int iTarget = a_cnrviTarget[i];
    int iRtn0, iRtn1;

    if (iRtn0 = fnRcsSearch(0, a_cnrviElement, iTarget, vviOK))
    {
      cout << "yes" << endl;
      vviOK[0][iTarget] = iRtn0;
      continue;
    }

    int iSmallTarget = iTarget - a_cnrviElement[0];
    if (iRtn1 = fnRcsSearch(0, a_cnrviElement, iSmallTarget, vviOK))
      cout << "yes" << endl;
    else
      cout << "no" << endl;

    if (iSmallTarget >= 0)
      vviOK[0][iSmallTarget] = iRtn1;
  }
}

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

  int iElementCnt, iTargetCnt;
  vector<int> viElement, viTarget;

  fnInput(iElementCnt, viElement, iTargetCnt, viTarget);
  fnExhSearch(viElement, viTarget);

  return 0;
}

Measured memory_bytes: 1344
#include <bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
int main(){
    long long n,k;
    cin >> n >> k;
    vector<long long>a(n);
    vector<long long>pos;//0以上の数を受け取る
    vector<long long>neg;//負の値を受け取る
    for(long long i=0;i<n;i++){
        long long x;
        cin >> x;
        a[i]=x;
        if(x>=0)pos.push_back(x);
        else neg.push_back(x);
    }
    sort(pos.begin(),pos.end());
    sort(neg.begin(),neg.end());//絶対値が大きい順
    reverse(pos.begin(),pos.end());//大きい順にする
    long long ans=1;
    //k=nの時
    if(k==n){
        for(long long i=0;i<n;i++){
            ans*=(a[i]+MOD);
            ans%=MOD;
        }
        cout << ans << endl;
        return 0;
    }
    //正の数がないとき
    if(pos.empty()){
        //答えが負になるとき絶対値の小さい順
        if(k%2){
            reverse(neg.begin(),neg.end());
            for(long long i=0;i<k;i++){
                ans*=(MOD+neg[i]);
                ans%=MOD;
            }
            cout << ans << endl;
            return 0;
        }
        //答えが正になるとき大きい順でとる
        else{
            for(long long i=0;i<k;i++){
                ans*=(MOD+neg[i]);
                ans%=MOD;
            }
            cout << ans << endl;
            return 0;
        }
    }

    //kが奇数の時正の数の最大値をあらかじめ取っておく
    if(k%2){
        ans*=pos[0];
        pos.erase(pos.begin());
    }

    long long p=pos.size();
    long long ne=neg.size();
    vector<long long>pos_pair(p/2);
    vector<long long>neg_pair(ne/2);
    for(long long i=0;i<p/2;i++){
        pos_pair[i]=(pos[i*2]*pos[i*2+1]);
    }
    for(long long i=0;i<ne/2;i++){
        neg_pair[i]=(neg[i*2]*neg[i*2+1]);
    }
    long long pk=0,nk=0;
    for(long long i=0;i<k/2;i++){
        if(pk==p/2){
            neg_pair[nk]%=MOD;
            ans*=neg_pair[nk];
            ans%=MOD;
            nk++;
        }
        else if(nk==ne/2){
            pos_pair[pk]%=MOD;
            ans*=pos_pair[pk];
            ans%=MOD;
            pk++;
        }
        else{
            if(pos_pair[pk]>neg_pair[nk]){
                pos_pair[pk]%=MOD;
                ans*=pos_pair[pk];
                ans%=MOD;
                pk++;
            }
            else{
                neg_pair[nk]%=MOD;
                ans*=neg_pair[nk];
                ans%=MOD;
                nk++;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 7172
N, M = map(int, input().split())

st = 1
en = N
for _ in range(M):
    L, R = map(int, input().split())
    st = max(st, L)
    en = min(en, R)

ans = en - st
if ans < 0:
    print(0)
else:
    print(ans + 1)


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

#define sz(x) int(x.size())
#define pii pair<int, int>
#define All(x) (x).begin(), (x).end()
#define mp make_pair
#define Task "abc"

typedef long long ll;
const int maxn = 1e4 + 10;
const ll mod = 1e9 + 7;

int n, m;
int c[] = {2, 5, 5, 4, 5, 6, 3, 7, 6};
int num[10], cost[10], ma[8];
int f[maxn], tr[maxn];

void Trace(int i){
  if (i == 0) return;
  int t = tr[i];
  cout << ma[i - t];
  Trace(t);
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(NULL);
//  freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout);
  cin >> n >> m;
  for (int i = 0; i < 10; ++i){
    cost[i+1] = c[i];
  }
  for (int i = 0; i < m; ++i){
    cin >> num[i];
    ma[cost[num[i]]] = max(ma[cost[num[i]]], num[i]);
  }
  sort(num, num + m);
  const int inf = 2e9;
  fill(f, f + maxn, -inf);
  f[0] = 0;
  for (int i = 2; i <= n; ++i) for (int j = 0; j < m; ++j){
    int l = cost[num[j]];
    if (num[j] != ma[l]) continue;
    if (i < l) continue;
    if (f[i] <= f[i-l] + 1){
      f[i] = f[i-l] + 1;
      tr[i] = i-l;
    }
  }
  Trace(n);
return 0;
}




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

#define ll long long
#define ull unsigned long long

using namespace std;

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

    for (ll a = -150; a < 150; ++a){
        for (ll b = -150; b < 150; ++b){
            ll a5 = a*a*a*a*a;
            ll b5 = b*b*b*b*b;
            if (a5 - b5 == N){
                cout << a << " " << b << endl;
                return 0;
            }
        }
    }

	return 0;
}


Measured memory_bytes: 3592
require 'pp'

n, k = gets.split.map(&:to_i)
memo = Hash.new(0)
k.times do |i|
    d = gets.to_i
    a_d = gets.split.map(&:to_i)
    
    a_d.each do |a|
        memo[a] += 1
    end
end

puts n - memo.keys.length


Measured memory_bytes: 14628
import java.util.Scanner;
import java.util.Arrays;

class Main{
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		
		while(true){
			String s = scanner.next();
			int sum = 0;

			for(int i = 0; i < s.length(); i++){
				char ch = s.charAt(i);
				sum += Character.getNumericValue(ch);
			}
			
			if(sum == 0){
			    break;
			}

			System.out.println(sum);
		}
	}
}

Measured memory_bytes: 26508
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    double ans = (double)((a+b)/2);
    if((a+b) % 2 == 0){
      System.out.println((int)ans);
    }else{
      System.out.println("IMPOSSIBLE");
    }
  }
}


Measured memory_bytes: 21972
#include <stdio.h>
#include <stdlib.h>

int main(){
  int a, b, m, i, j, tmp, minA = 10000000, minB = 10000000, min = 1000000000;
  if (scanf("%d", &a) == EOF ){
    exit(1);
  }
  if (scanf("%d", &b) == EOF ){
    exit(1);
  }
  if (scanf("%d", &m) == EOF ){
    exit(1);
  }
  int arrayA[a], arrayB[b], arrayM[m][3];

  for (i = 0; i < a; i++){
    if (scanf("%d", &arrayA[i]) == EOF){
      exit(1);
    }
  }
  for (i = 0; i < b; i++){
    if (scanf("%d", &arrayB[i]) == EOF){
      exit(1);
    }
  }
  for (i = 0; i < m; i++){
    if (scanf("%d %d %d", &arrayM[i][0], &arrayM[i][1], &arrayM[i][2]) == EOF){
      exit(1);
    }
  }
  for (i = 0; i < a; i++){
    tmp = arrayA[i];
    if (minA > tmp){
      minA = tmp;
    }
  }
  for (i = 0; i < b; i++){
    tmp = arrayB[i];
    if (minB > tmp){
      minB = tmp;
    }
  }
  min = minA + minB;
  for (i = 0; i < m; i++){
    tmp = arrayA[arrayM[i][0]-1] + arrayB[arrayM[i][1]-1] -arrayM[i][2];
    if (min > tmp){
      min = tmp;
    }
  }
  printf("%d", min);
  return 0;
}


Measured memory_bytes: 2176
#include <iostream>
#include <string.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int d[10005];
int main()
{
    int t;
    cin>>t;
    int a,b;
    cin>>a>>b;
    int ans=1;
    int mog;
    int g;
    for(int i=1;i<=t;i++)
    {
        cin>>d[i];
        if(abs(a*1000-d[i]*6-b*1000)<abs(a*1000-6*d[ans]-b*1000))
        {
            ans=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef signed long long ll;
 
#define REP(i,a,b) for(i=(int)a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(a) (a).begin(), (a).end()

int main(){
	int i,j,k,n,m,l,f,x,y,z; string s;
	cin >> n;
  	float sum = 0;
 	rep(i, n){
      float a;
      cin >> a;
      sum += 1/a;
    }
  	
  	cout << 1 / sum << endl;
}

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

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i].first;
        A[i].second = i;
    }
    sort(A.begin(), A.end(), greater<pair<int, int>>());
    for (int i = 0; i < N; ++i) {
        if (A[0].second == i)
            cout << A[1].first << endl;
        else
            cout << A[0].first << endl;
    }

}

Measured memory_bytes: 3200
//Atcoder Begineer Contest102
//B - Maximum Difference
//2018/07/01 20:47

#include<stdio.h>
#define MAX 100

int main(void)
{
  int i;
  int N;
  int A[MAX]={};
  int max = 0;
  int min = 1000000000;

  scanf("%d",&N);

  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
    if(min>=A[i]){
      min = A[i];
    }
    if(max<=A[i]){
      max = A[i];
    }
  }

  printf("%d\n",max-min);

  return 0;
}


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




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

    int N;
    cin >> N;
    ll ans = 0;
    reps(i,1,N+1){
        if(i%3 == 0) continue;
        if(i%5 == 0) continue;
        
        ans += (ll)i;
    }
    
    cout << ans << endl;
    
    
    

    return 0;
}


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

using namespace std;

int main()
{
    string s;
    cin>>s;
    int x=s.back();
    if(x=='2'||x=='4'||x=='5'||x=='7'||x=='9')cout<<"hon"<<endl;
    else if(x=='0'||x=='1'||x=='6'||x=='8')cout<<"pon"<<endl;
    else if(x=='3')cout<<"bon"<<endl;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef map<int,int> mii;
#define pb push_back

int An(double h, double m)  
{  
    // validate the input  
    if (h <0 || m < 0 || h >12 || m > 60)  
        printf("Wrong input");  
  
    if (h == 12) h = 0;  
    if (m == 60) m = 0;  
  
    // Calculate the angles moved  
    // by hour and minute hands  
    // with reference to 12:00  
    int hour_angle = 0.5 * (h * 60 + m);  
    int minute_angle = 6 * m;  
  
    // Find the difference between two angles  
    int angle = abs(hour_angle - minute_angle);  
  
    // Return the smaller angle of two possible angles  
    angle = min(360 - angle, angle);  
  
    return angle;  
}  
  
int main()
{
    int tst=1;
	//scanf("%d",&tst);
    while(tst--)	
	{
		double a,b,h,m;
		cin >> a >> b >> h >> m;
		double an=(60*h)-(11*m);
		an/=2;
		if(an>180)
		{
			an=360-an;
		}
		//cout << an << endl;
		an=(acos(-1)*an)/180;
		double c;
		c=(a*a)+(b*b)-(2*a*b*cos(an));
		c=sqrt(c);
		cout << fixed << setprecision(22) << c << endl;
	}
    return 0;
}


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

void fnInput(vector<string>& rvsBoard)
{
  int nHigh, nWide;
  cin >> nHigh >> nWide;

  rvsBoard.resize(nHigh);
  for (int ny = 0; ny < nHigh; ny++)
    cin >> rvsBoard[ny];
}

int fnCountBomb(int ny, int nx, const vector<string>& cnrvsBoad)
{
  if (   ny >= 0  && ny < cnrvsBoad.size()
      && nx >= 0  && nx < cnrvsBoad[ny].size())
    if (cnrvsBoad[ny][nx] == '#')  return 1;
    else;

  return 0;
}

void fnMinesweeper(vector<string>& rvsBoard)
{
  const vector<int> cnvnDy = {-1, -1, -1,  0,  0,  1,  1,  1};
  const vector<int> cnvnDx = {-1,  0,  1, -1,  1, -1,  0,  1};
  for (int ny = 0; ny < rvsBoard.size(); ny++)
  {
    for (int nx = 0; nx < rvsBoard[ny].size(); nx++)
    {
      if (rvsBoard[ny][nx] == '.')
      {
        int nCount = 0;
        for (int i = 0; i < cnvnDx.size(); i++)
          nCount += fnCountBomb(ny + cnvnDy[i], nx + cnvnDx[i], rvsBoard);

        rvsBoard[ny][nx] = '0' + nCount;       // int → char 変換
      }
    }
  }
}

void fnResult(const vector<string>& cnrvsBoard)
{
  for (string sBoard : cnrvsBoard)
    cout << sBoard << endl;
}

int main()
{
  vector<string> vsBoard;

  fnInput(vsBoard);
  fnMinesweeper(vsBoard);
  fnResult(vsBoard);

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int W,H,x,y,r;
  scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
  if(x,y>0 && x-r>=0 && y-r>=0 && x+r<=W && y+r<=H){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

const ll MOD=1e9+7;

ll ad(ll x,ll y=0){
  return (x+y)%MOD;
}

ll mlt(ll x,ll y=1){
  return (x*y)%MOD;
}

int main(){
  ll n,a[26]={},k=1;
  char s;
  cin>>n;
  fr(i,n){cin>>s;a[s-'a']++;}
  fr(i,26) k=mlt(k,a[i]+1);
  cout<<ad(k,MOD-1)<<endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M,a;
  a=0;
  cin>>N>>M;
  for(int i=0;i<M;i++){
    int b;
    cin>>b;
    a+=b;
  }
  if(a<=N){
    cout<<N-a<<endl;
  }
  else{
    cout<<-1<<endl;
  }
}

Measured memory_bytes: 3596
n=int(input())
p=list(map(int,input().split()))
s=0
for i in range(1,n-1):
    if p[i-1]<=p[i]<=p[i+1]:
        s+=1
    elif p[i+1]<=p[i]<=p[i-1]:
        s+=1
    else:
        s+=0
print(s)

Measured memory_bytes: 3060
def resolve():
    import itertools
    import math
    def distance(i, j):
        return math.sqrt((i[0]-j[0])**2+(i[1]-j[1])**2)

    n = int(input())
    l = list(range(n))
    X_Y = []
    for i in range(n):
        X_Y.append(list(map(int, input().split())))
    p_list = list(itertools.permutations(l, n))
    total = 0
    for p in p_list:
        p_t = 0
        for index in range(n-1):
            p_t += distance(X_Y[p[index]], X_Y[p[index+1]])
        total += p_t
    print(total/len(p_list))
resolve()

Measured memory_bytes: 13912
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<math.h>
#include<stack>
#include<set>
#include<map>
#define INF 2e9
#define rep(i,n,m) for(int i=n;i<m;i++)

using namespace std;

int main()
{
	int h, w, n;
	cin >> h >> w >> n;
	int ans = 0;
	if (h > w) {
		while (n>0) {
			ans++;
			n -= h;
		}
	}
	else {
		while (n>0) {
			ans++;
			n -= w;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3588
#include<iostream>
using namespace std;
 
int main(){
  int worker_num, boss_num;
  int i;

  int A[2*100000]={0};

  cin >> worker_num;
  
  for(i=0; i<worker_num-1; i++){
    cin >> boss_num;
    A[boss_num-1]++;
  }

  for(i=0; i<worker_num; i++){
    cout << A[i] << endl;
  }
}

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

#define REP( i, n) for( int i = 0; i < (n); ++i)
#define FOR( i, a, b) for( int i = (a); i < (b); ++i)

using namespace std;

int n;
int s;
int ans;
int a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

int dfs( int x, int i, int sum){

  if( x == n && sum == s){
    ++ans;
  }else{
    if( i < 10){
      dfs( x+1, i+1, sum+a[i]);
      dfs( x, i+1, sum);
    }else{
      return ans;
    }
  }
}

int main(){

  while(1){
    ans = 0;
    cin >> n >> s;
    if( n == 0 && s == 0){
      break;
    }

    cout << dfs( 0, 0, 0) << endl;
  }
  return 0;
}

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

int main()
{
	double x1,y1,x2,y2,x3,y3,xp,yp;
	while(cin>>x1>>y1>>x2>>y2>>x3>>y3>>xp>>yp)
	{
		complex<double> p1(x1,y1),p2(x2,y2),p3(x3,y3),pp(xp,yp);
		if ( arg((p3-p1)/(p2-p1))*arg((pp-p1)/(p2-p1))>0 &&
			 arg((p1-p2)/(p3-p2))*arg((pp-p2)/(p3-p2))>0 &&
			 arg((p2-p3)/(p1-p3))*arg((pp-p3)/(p1-p3))>0 )
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
			 
	}

	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define mod 1000000007 //10^9+7
#define INF 1000000000000 //10^12
#define P pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
int n,ans=0;
int a[150];
signed main(){
    cin>>n;
    rep(i,n)cin>>a[i];
    for(int i=1;i<n;i++){
        if(a[i]==a[i-1]){
            ans++;
            i++;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <functional>
#include <map>
#include <bitset>

#define INF 0x7fffffff
#define REP(i,j,k) for(int i = j;i <= k;i++)
#define squr(x) (x) * (x)
#define lowbit(x) (x&(-x))
#define getint(x) scanf("%d", &(x))

typedef long long LL;

using namespace std;
const int MAXN = 110;
int n, m;
int a[MAXN];

int f[MAXN];

int main(int argc, const char * argv[]) {
    getint(n);
    int d = 0, l = INF;
    REP(i, 1, n) {
        getint(a[i]);
        d = max(d, a[i]);
        l = min(l, a[i]);
        f[a[i]]++;
    }
    
    if (l != (d + 1) / 2 || f[d] < 2) {
        cout << "Impossible" << endl;
        return 0;
    }
    
    if (d % 2 == 0) {
        if (f[l] != 1) {
            cout << "Impossible" << endl;
            return 0;
        }
    } else {
        if (f[l] != 2) {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    
    for (int i = l + 1; i < d; i++) {
        if (f[i] < 2) {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    
    cout << "Possible" << endl;
    
    return 0;
}










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

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

using namespace std;

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

  cout << fixed << setprecision(7);
  if(N%2==0) cout << 1/2. << endl;
  else cout << (N+1)/2./N << endl;    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
int n, a[N], L;

int main() {
    cin >> n >> L;
    int mx = 0, v;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++)
    if (a[i] + a[i+1] > mx) {
        mx = a[i] + a[i+1];
        v = i;
    }
    if (mx < L) {
        cout << "Impossible" << endl;
        return 0;
    }
    cout << "Possible" << endl;
    for (int i = 1; i < v; i++) cout << i << endl;
    for (int i = n - 1; i >= v; i--) cout << i << endl;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int main()
{long long x=0,k=0,d=0,d1=0,s1=0,s2=0;
    cin>>x>>k>>d;
 if(x<0)
   x=-(x);
    if(x==0)
    {if((k%2)==1)
    cout<<x+d;
        else
        cout<<x;
    }
    else
    {
    d1=x/d;
    if(d1>=k)
    cout<<(x-(k*d));
    else
    {
        s1=x-(d1*d);
        s2=-(s1-d);
        if(s1<=s2)
        {
            if((k-d1)%2==0)
            cout<<s1;
            else
            cout<<s2;
        }
        else
        {
            if((k-(d1+1))%2==0)
            cout<<s2;
            else
            cout<<s1;
        }
    }}
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
    int N;
    cin >> N;
    ll res = -1;
    while(N--) {
        ll T;
        cin >> T;
        if(res == -1) {
            res = T;
            continue;
        }
        ll g = __gcd(res, T);
        res /= g;
        res *= T;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
// Etavioxy
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#define il inline
#define ll long long
#define rep(i,s,t) for(register int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(register int i=(s);i>=(t);i--)
#define each(i,u) for(int i=head[u];i;i=bow[i].nxt)
#define file(s) freopen(s".in" ,"r",stdin),freopen(s".out","w",stdout)
#define pt(x) putchar(x)
using namespace std;
il int ci(){
	register char ch;int f=1;
	while(!isdigit(ch=getchar()))f=ch=='-'?-1:1;
	register int x=ch^'0';
	while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
	return f*x;
}

ll gcd(ll a,ll b){
	return b==0 ? a:gcd(b,a%b) ;
}

int main(){
	ll a=ci(), b=ci();
	ll g=gcd(a,b);
	printf("%lld\n",a*b/g);
	return 0;
}


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

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

	int lim = s.size();

	for(int i = 0; i < lim; i++){
        int dif = 'z'-s[i];
		
        if(dif + 1 <= k && s[i] != 'a'){
			k -= dif + 1;
			s[i] = 'a';
		}

		if(i == lim-1){
			k %= 26;
			for(int j = 0; j < k; j++){
				if(s[i] == 'z') s[i] = 'a';
				else s[i]++;
			}
		
        }
        
	}

    cout<<s<<endl;

	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#define _USE_MATH_DEFINES
#include <cmath>

using namespace std;
typedef pair<double, double> P;
P point[1001];

void calc()
{
	double theta = M_PI / 4;
	point[2].first = 1.0;
	point[2].second = 1.0;
	for(int i = 2; i < 1000; ++i)
	{
		theta += atan(1 / sqrt((double)i));
		point[i + 1].first = sqrt((double)i + 1) * cos(theta);
		point[i + 1].second = sqrt((double)i + 1) * sin(theta);
	}
}

void solve()
{
	calc();
	int n;
	while(true)
	{
		cin >> n;
		if(n == -1)
		{
			break;
		}
		printf("%.2f\n%.2f\n", point[n].first, point[n].second);
	}
}

int main()
{
	solve();
	return(0);
}

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

#define int long long
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define popcount __builtin_popcountll

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

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";
}

template <typename A>
string to_string(vector<A> v) {
    bool first = true;
    string result = "[";
    for (A i : v) {
        if (!first) result += ", ";
        first = false;
        result += to_string(i); 
    }
    return result + "]";
}

template <typename A>
string to_string(A x[], int n) {
    string result = "{";
    REP(i, 0, n) {
        if (i!=0) result += ", ";
        result += to_string(x[i]); 
    }
    return result + "}";
}

string bin_string(int x) {
    const int d = 64;
    string result(d, ' ');
    RREP(i, d-1, -1) result[d-1-i] = '0'+((x&1LL<<i)!=0);
    return result;
}

vector<int> getZ(string s) {
    int n = s.size();
    vector<int> z(n);
    int x = 0, y = 0;
    REP(i, 1, n) {
        z[i] = max(0LL, min(z[i-x], y-i+1));
        while (i+z[i] < n && s[z[i]] == s[i+z[i]]) {
            x = i;
            y = i+z[i];
            ++z[i];
        }
    }
    return z;
}

int powa(int base, int exp) {
    if (exp<=0) return 1;
    if (base<=0) return 0;
    int val = powa(base, exp>>1);
    val = val*val % MOD;
    if (exp&1) {
        val = val*base % MOD;
    }
    return val;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    const int INNER = 80*160+10;
    const int OUTER = INNER+100;

    int R,C;
    cin >> R >> C;
    int grid[R][C];

    REP(r, 0, R)
        REP(c, 0, C)
            cin >> grid[r][c];
    
    REP(r, 0, R) {
        REP(c, 0, C) {
            int x;
            cin >> x;
            grid[r][c] = abs(grid[r][c]-x);
        }
    }

    bitset<2*OUTER> dp[R][C];
    dp[0][0][OUTER+grid[0][0]] = dp[0][0][OUTER-grid[0][0]] = 1;
    REP(r, 0, R) {
        REP(c, 0, C) {
            REP(k, OUTER-INNER, OUTER+INNER) {
                if (r == 0 && c == 0) continue;
                dp[r][c][k] = r!=0 && (dp[r-1][c][k-grid[r][c]] || dp[r-1][c][k+grid[r][c]]) || c!=0 && (dp[r][c-1][k-grid[r][c]] || dp[r][c-1][k+grid[r][c]]);
            }
        }
    }
    
    int res=0;
    while (!dp[R-1][C-1][OUTER+res] && !dp[R-1][C-1][OUTER-res]) ++res;
    cout << res;
}

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

l = [1]*(N+2)
p = [1]*(N+2)


for i in range(N+1):
	l[i+1] = 2*l[i]+3
	p[i+1] = 2*p[i]+1

def dfs(level,dist):
	ans = 0
	if level==0:
		return 1
	elif dist==1:
		return 0
	elif dist==l[level]:
		return p[level]
	elif dist==2+l[level-1]:
		return p[level-1]+1
	else:
		if dist <= 1+l[level-1]:
			ans = dfs(level-1,dist-1)
		else:
			ans = p[level-1]+1+dfs(level-1,dist-2-l[level-1])
	return ans

print(dfs(N,K))


Measured memory_bytes: 3064
#include <stdio.h>
#include <math.h>

int main(void){
	int a[4],b[4],t,c=0,d=0,f;
	scanf("%d %d %d %d",&a[0],&a[1],&a[2],&a[3]);
	scanf("%d %d %d %d",&b[0],&b[1],&b[2],&b[3]);
	
	for(t=0;t<4;t++){
		c+=a[t];
		d+=b[t];
	}
	f=fmax(c,d);
	printf("%d\n",f);
return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()

int main(){
  ll k, x; cin >> k >> x;
  ll A = 1e6;
  ll lb = max(-A,x-k+1);
  ll ub = min(A, x+k-1);
  FOR(i,lb,ub+1){
    cout << i;
    if(i==ub) cout << endl;
    else cout << " "; 
  }
}


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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int H, W;
int di[2] = {0, 1}, dj[2] = {1, 0};
int A[85][85], B[85][85];
bool DP[85][85][int(4e4 + 5)];

int main(){
  cin >> H >> W;
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      cin >> A[i][j];
    }
  }
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      cin >> B[i][j];
    }
  }

  DP[0][0][A[0][0] - B[0][0] + int(2e4)] = true;
  DP[0][0][B[0][0] - A[0][0] + int(2e4)] = true;

  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      for (int k = 0; k <= int(4e4); k++){
        if (!DP[i][j][k]) continue;
        for (int l = 0; l < 2; l++){
          int I = i + di[l], J = j + dj[l];
          DP[I][J][k + (A[I][J] - B[I][J])] = true;
          DP[I][J][k + (B[I][J] - A[I][J])] = true;
        }
      }
    }
  }

  int ans = 1e9;
  for (int k = 0; k <= int(4e4); k++){
    if (DP[H-1][W-1][k]){
      ans = min(ans, abs(k-int(2e4)));
    }
  }
  cout << ans << endl;

  return 0;
}


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

bool cmp(pair<ll,ll>a,pair<ll,ll>b)
{
	if(a.first!=b.first)return a.first>b.first;
	return a.second>b.second;
}

int main()
{
	int n,k;
	cin >> n >> k;
	vector<pair<ll,ll>> cmt,a,b;
	map<ll,ll> mp;
	for(int i = 0;i<n;i++)

	{
		ll x,y;
		cin >> x >> y;
		cmt.emplace_back(y,x);
	}
	sort(cmt.begin(),cmt.end(),cmp);
	for(int i = 0;i<n;i++)
	{
		ll x;
		x = cmt[i].second;
		ll y ;
		y = cmt[i].first;
		if(mp[x]==0)
		{
			a.emplace_back(y,x);
			mp[x] = true;
		}
		else
		{
			b.emplace_back(y,x);
		}
	}
	set<int> st;
	
	sort(a.begin(),a.end(),cmp);
	sort(b.begin(),b.end(),cmp);
	vector<ll> asum(a.size()+1),bsum(b.size()+1);
	for(int i = 0;i<a.size();i++)
	{
		asum[i+1] += a[i].first+asum[i];
	}
	for(int i = 0;i<b.size();i++)
	{
		bsum[i+1] += b[i].first+bsum[i];
	}
	ll ans = 0;
	set<ll> A,B;
	
	for(int i = 1;i<=k;i++)
	{
		ll now = 0;

		if(i<asum.size())
		{
			now += asum[i];
			A.insert(a[i-1].second);
			if(B.find(a[i-1].second)!=B.end())
			{
				B.erase(B.find(a[i-1].second));
			}
		}
		else continue;
		if(k-i<bsum.size())
		{
			now += bsum[k-i];
			if(A.find(a[i-1].second)==A.end())B.insert(b[i-1].second);
		}
		else continue;
		ll x = A.size()+B.size();
		now += x*x;
		ans = max(ans,now);
	}
	cout<<ans<<endl;


}

Measured memory_bytes: 12784
#include <stdio.h>

#define MAX 512

int N;
int C[MAX], S[MAX], F[MAX];

int main(void) {
	int i, j;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i < N; i++) {
		if (scanf("%d%d%d", &C[i], &S[i], &F[i]) != 3) return 1;
	}
	for (i = 1; i <= N; i++) {
		int cur = 0;
		for (j = i; j < N; j++) {
			int dept;
			if (cur < S[j]) {
				dept = S[j];
			} else {
				dept = S[j] + (((cur - S[j]) + F[j] - 1) / F[j]) * F[j];
			}
			cur = dept + C[j];
		}
		printf("%d\n", cur);
	}
	return 0;
}


Measured memory_bytes: 128
/******************** Beginning of Template **************************/
/************ ALL HEADER FILE ***********/
//#include<bits/stdc++.h>
#include <iostream>
using namespace std;

/************************************ ALL DEFINE ****************************************************/
#define FORS(i, j, k, step) for (int i=j; i<k; i+=step)
#define FOR(i, j, k) for (int i=j; i<k; i++)
#define RFORS(i, j, k, step) for (int i=j; i>=k; i-=step)
#define RFOR(i, j, k, step) for(int i=j; i>=k; i--)
#define REP(i, k) for(int i = (0); i < (k); i++ )
#define RREP(i, k) for(int i = j; i >= (k); i-- )

#define ALL(cont) cont.begin(), cont.end()
#define RALL(cont) cont.begin(), cont.end()
#define FOREACH(it, l) for(auto it=l.begin(); it != l.end(); it++)
#define mp make_pair
#define pb push_back
#define RESET(a, b) memset(a, b, sizeof(a))
#define INF (int)MAX_INT
#define EPS (int)1e-9
#define PI acos(-1)
#define MOD 1000000007
#define fango using
#define ganteng namespace
#define sekali std

/*********************************Debug DEFINE  ********************************/
#define TESTING
//#define FILE_INPUT
//#define FILE_OUTPUT
/*********************************END of Debug DEFINE  ********************************/

#ifdef TESTING
#define VALUE(x) cout << ">>>> The value of " << #x << " is " << x << "<<<<" << endl
#define NEWLINE cout << "---------------------------------------------" << endl
#define DUMP_STR cout << ">>>>FANGO IS THE MOST HANDSOME MANKIND IN THE ENTIRE WORLD<<<<" << endl;
#define DUMP_CHAR cout << " YO ";
#endif //TESTING_ON_CONSOLE



/************************************ END OF DEFINE ****************************************************/

/************************************ ALL TYPEDEF ****************************************************/
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<piii> viii;
typedef long long int32;
typedef unsigned long long uint32;
typedef long long int int64;
typedef unsigned long long int uint64;



/************************************ ALL DEFINE ****************************************************/

/************************************ END OF PREHEADER ***********************************************/



void solve() {
	int a, b, c;
	cin >> a >> b >> c;

	int ans = a - b;

	if (c >= ans) {
		cout << c - ans;
	} else {
		cout << "0";
	}

}

int main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int TC = 1;
	//cin >> TC;

	while (TC--) {

		solve();
	}
}

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

int main(){
    int N;
    string str;
    cin >> N;
    cin >> str;

    int ans = 0;
    char buf = 'X';

    for (int i = 0; i < N; i++){
        if (str[i] != buf){
            ans++;
            buf = str[i];
        }
    }

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 512
import math
N, A, B = map(int, input().split())
h = [int(input()) for _ in range(N)]

sup = 10**9
inf = 0
add = A-B


def binary(check):
    count = check
    for i in range(N):
        ch = h[i] - B*check
        if ch <= 0:
            continue
        else:
            count -= math.ceil(ch/add)
        if count < 0:
            break
    if count < 0:
        return False
    else:
        return True


while sup > inf+1:
    p = (sup+inf)//2
    if binary(p):
        sup = p
    else:
        inf = p
print(sup)


Measured memory_bytes: 7068
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
using namespace std;
string grid[20];
bool used[20][20];
int move_h[4] = {-1, 1, 0, 0};
int move_w[4] = {0, 0, -1, 1};

void dfs(int cur_h, int cur_w, int h, int w){
  used[cur_h][cur_w] = true;
  for(int i = 0; i < 4; i++){
    int next_h = cur_h + move_h[i];
    int next_w = cur_w + move_w[i];
    if(0 <= next_h && next_h < h && 0 <= next_w && next_w < w
        && !used[next_h][next_w] && grid[next_h][next_w] != '#'){
      dfs(next_h, next_w, h, w);
    }
  }
}

int main(){
  while(true){
    int W;
    int H;
    cin >> W >> H;
    if(W == 0 && H == 0){
      break;
    }
    for(int i = 0; i < H; i ++){
      cin >> grid[i];  
    }

    int start_h = 0;
    int start_w = 0;
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        used[i][j] = false;
        if(grid[i][j] == '@'){
          start_h = i;
          start_w = j;
        }
      }
    }

    dfs(start_h, start_w, H, W);

    int ans = 0;
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        if(used[i][j]){
          ans ++;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3044
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	string x; cin >> x;
	stack<int> st;
	for (auto i : x)
	{
		if (i == 'S') st.push(0);
		else
		{
			if (!st.empty() && st.top() == 0) st.pop();
			else st.push(1);
		}
	}
	cout << st.size() << endl;
	return 0;
}

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

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>
long MOD = 1000000007;

int main() {
    int N, M;
    cin>>N>>M;
    vl X(N), Y(M);
    REP(i, 0, N) cin >> X[i];
    REP(i, 0, M) cin >> Y[i];
    vector<long long> X_T(N), Y_T(M), X_Mer(N), Y_Mer(M);
    X_T[0] = N-1; X_T[N-2] = N-1;
    Y_T[0] = M-1; Y_T[M-2] = M-1;
    REP(i, 0, N-1) X_Mer[i] = X[i+1]- X[i];
    REP(i, 0, M-1) Y_Mer[i] = Y[i+1]- Y[i];
    REP(i, 1, (N+1)/2) X_T[i] = X_T[N - 2 - i] = (X_T[i-1] +  N - 1 - i * 2) % MOD; 
    REP(i, 1, (M+1)/2) Y_T[i] = Y_T[M - 2 - i] = (Y_T[i-1] + M - 1 - i * 2) % MOD; 

    long long X_sum = 0, Y_sum = 0;
    REP(i, 0, N-1){
        X_sum += X_Mer[i] * X_T[i] % MOD;
        X_sum %= MOD;
    }    
    REP(i, 0, M-1){
        Y_sum += Y_Mer[i] * Y_T[i] % MOD;
        Y_sum %= MOD;
    }
    long long ans = X_sum * Y_sum % MOD;
    cout << ans << endl;
    /*
    REP(i, 0, N-1) cout << X_T[i] << " ";
    cout << endl;
    REP(i, 0, M-1) cout << Y_T[i] << " ";
    cout << endl;
    */
}

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

using namespace std;

using int64 = long long;

struct Int2D {
  int64 x, y;
};

// Vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	int len = v.size();
  s << "[";
	for (int i = 0; i < len; i++) {
    if (i > 0) s << ", ";
		s << v[i];
	}
  s << "]";
	return s;
}

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

  cout << fixed << setprecision(12);

  Int2D s, t;
  cin >> s.x >> s.y >> t.x >> t.y;
  int n;
  cin >> n;
  vector<Int2D> ps;
  for (int i = 0; i < n; i++) {
    Int2D p;
    cin >> p.x >> p.y;
    ps.push_back(p);
  }

  auto transform1_fn = [s, t](Int2D& p) {
    if (s.x > t.x) {
      p.x *= -1;
    }
    if (s.y > t.y) {
      p.y *= -1;
    }
  };
  transform1_fn(s);
  transform1_fn(t);
  for (int i = 0; i < n; i++) transform1_fn(ps[i]);

  auto transform2_fn = [s, t](Int2D&p) {
    if (s.x == t.x) {
      swap(p.x, p.y);
    }
  };
  transform2_fn(s);
  transform2_fn(t);
  for (int i = 0; i < n; i++) transform2_fn(ps[i]);

  sort(ps.begin(), ps.end(), [](const auto& p1, const auto& p2) {
    return p1.x < p2.x;
  });

  vector<int64> ys;
  for (const auto& p : ps) {
    if (s.x <= p.x && p.x <= t.x && s.y <= p.y && p.y <= t.y) {
      ys.push_back(p.y);
    }
  }
  // cerr << "ys: " << ys << endl;

  int m = ys.size();
  vector<int64> dp(m, INT64_MAX);
  for (int64 y : ys) {
    int k = distance(dp.begin(), lower_bound(dp.begin(), dp.end(), y));
    // cerr << "k: " << k << endl;
    dp[k] = y;
  }
  int count = 0;
  for (int64 v : dp) {
    if (v < INT64_MAX) count++;
  }
  // cerr << "count: " << count << endl;

  if (count == min(t.x - s.x + 1, t.y - s.y + 1)) {
    double ans = 100.0 * (t.x - s.x + t.y - s.y)
        + (count - 1) * (5.0 * M_PI - 20) + (10.0 * M_PI - 20);
    cout << ans << endl;
  } else {
    double ans = 100.0 * (t.x - s.x + t.y - s.y)
        + count * (5.0 * M_PI - 20);
    cout << ans << endl;
  }
}

Measured memory_bytes: 7660
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        long[] b = new long[n];
        for (int i = 0 ; i < n ; i++) {
            a[i] = sc.nextLong();
            b[i] = sc.nextLong();
        }

        long count = 0;
        for (int i = n - 1 ; i >= 0 ; i--) {
            if ((a[i] + count) % b[i] != 0) {
                count += b[i] - ((a[i] + count) % b[i]);
            }

        }

        System.out.println(count);

    }

}

Measured memory_bytes: 87620
#include<bits/stdc++.h>
const int N=1e6+5,mo=998244353;
int vf[N],fac[N],inv[N];
inline int C(int n,int m){return n>=m?1ll*vf[m]*vf[n-m]%mo*fac[n]%mo:0;}
int n,k,r,b,t,i,ans;
int main(){
	for(i=*vf=*fac=1;i<N;++i)
		inv[i]=i==1?1:1ll*(mo-mo/i)*inv[mo%i]%mo,
		vf[i]=1ll*vf[i-1]*inv[i]%mo,
		fac[i]=1ll*fac[i-1]*i%mo;
	scanf("%d%d",&n,&k);r=k/2+1;
	if(k%2==0 && k/2>=n)t=k/2-n,ans=(C(k-1,k/2)+mo-C(k-1,k/2+t+1))%mo;
	for(r=std::max(r,n);r<=k;++r)b=k-r,t=r-n,ans=(ans+1ll*C(k,r)+mo-C(k,r+t+1))%mo;
	printf("%d\n",ans);
}

Measured memory_bytes: 12032
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x*x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define loop(n) FOR(i,0,n)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

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

	for (LL i = 0; i < k; i++) {
		if (i % 2 == 0) {
			if (a % 2 == 1) {
				a--;
			}

			b += (LL)a / 2;
			a /= 2;
		}
		else {
			if (b % 2 == 1) {
				b--;
			}

			a += (LL)b / 2;
			b /= 2;
		
		}
	}

	cout << a << " " << b << endl;

	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter pw = new PrintWriter(System.out);

        char[] s = sc.next().toCharArray();

        Stack<Integer> stack1 = new Stack<>();
        Stack<int[]> stack2 = new Stack<>();

        int sum = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '\\') {
                stack1.push(i);
            } else if (s[i] == '/' && stack1.size() > 0) {
                int j = stack1.pop();
                int area = i - j;
                sum += area;
                while (stack2.size() > 0 && stack2.peek()[0] > j) {
                    int[] a = stack2.pop();
                    area += a[1];
                }
                stack2.push(new int[]{j, area});
            }
        }

        List<Integer> ans = new ArrayList<>();
        while (!stack2.isEmpty()) {
            int[] a = stack2.pop();
            ans.add(0, a[1]);
        }

        pw.println(sum);
        pw.print(ans.size());
        for (int i = 0; i < ans.size(); i++) {
            pw.print(" " + ans.get(i));
        }
        pw.println();
        pw.flush();
    }

    static class MyScanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

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

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


Measured memory_bytes: 26388
#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> p(n);
  rep(i, n) cin >> p[i];

  ll res = 0;
  rep(i, n) {
    if (p[i] == i + 1) {
      if (i != n - 1) {
        swap(p[i], p[i + 1]);
      }
      res++;
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 640
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = array[-1] + 1
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = 0
    for x in array:
        if counter[x] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 32376