akhauriyash/Code-Regression huggingface dataset:
def charge(x, y, h, w):
  size = x + y + h
  if size <= 60 and w <= 2:
    return 600
  elif size <= 80 and w <= 5:
    return 800
  elif size <= 100 and w <= 10:
    return 1000
  elif size <= 120 and w <= 15:
    return 1200
  elif size <= 140 and w <= 20:
    return 1400
  elif size <= 160 and w <= 25:
    return 1600
  else:
    return 0
while True:
  n = int(input())
  if n == 0:
    break
  
  c_sum = 0 
  for _ in range(n):
    x, y, h, w = map(int, input().split())
    c_sum += charge(x, y, h, w)
  print(c_sum)


Measured memory_bytes: 5612
#include<bits/stdc++.h>
using namespace std;
int L,len,cnt,tong[100];
char ch[100];
vector<char> Ans;
vector<char> merge(int l,int r)
{
	vector<char> ret,ls,rs;
	if(l==r){
		for(int i=1;i<=tong[l];i++) ret.push_back(ch[l]);
		return ret;
	}
	int mid=(l+r)>>1,l1,l2; char ans[130];
	ls=merge(l,mid); rs=merge(mid+1,r);
	l1=ls.size(); l2=rs.size();
	if(!l1||!l2) {
		for(int i=1;i<=l1;i++) ret.push_back(ls[i-1]);  
		for(int i=l1+1;i<=l1+l2;i++) ret.push_back(rs[i-l1-1]);
		return ret; 
	}
	if(l1<l2) swap(l1,l2),swap(ls,rs);
	int lst=1; char s[130];
	for(int i=1;i<=l1;i++) s[i]=ans[i]=ls[i-1];
	for(int i=0;i<l2;i++)
	{
		int now=L-l1;
		for(int k=lst;k<=l1+1;k++)
		{
			for(int l=1;l<=l1+1;l++)
				if(l==k){
					for(int r=l;r<=l1;r++) s[r+1]=ans[r];
					s[l]=rs[i]; break;
				}
				else s[l]=ans[l];
			int tmp; printf("? "); cnt++;
			for(int l=1;l<=l1+1;l++) printf("%c",s[l]); puts("");
			fflush(stdout);
			scanf("%d",&tmp); 
			if(tmp==now-1) {
				for(int l=1;l<=l1+1;l++) ans[l]=s[l];
				lst=k+1; l1++; break;
			}
		}
	}
	for(int i=1;i<=l1;i++) ret.push_back(s[i]);
	return ret;
}
int main()
{
	for(int i=1;i<=26;i++) ch[i]='a'+i-1;
	for(int i=1;i<=26;i++) ch[i+26]='A'+i-1;
	for(int i=0;i<=9;i++) ch[i+53]='0'+i;
	for(int i=1;i<=62;i++)
	{
		printf("? "); cnt++; 
		for(int j=1;j<=128;j++) printf("%c",ch[i]); puts("");
		fflush(stdout);
		scanf("%d",&tong[i]); tong[i]=128-tong[i]; L+=tong[i];
	}
	Ans=merge(1,62);// cerr<<cnt<<" ";
	printf("! "); for(int i=1;i<=L;i++) printf("%c",Ans[i-1]); puts("");
	fflush(stdout);
}

Measured memory_bytes: 3776
#include <stdio.h>

int main(void)
{
	int a,b,c,e,d,f;
	
	scanf("%d %d %d",&a,&b,&c);
	
	e=a+b;
	f=b+c;
	d=a+c;
	
	if(e<=f&&e<=d)printf("%d\n",e);
	else if(f<=e&&f<=d)printf("%d\n",f);
	else printf("%d\n",d);
	
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <numeric> //lcm
#include <iomanip> //double精度 setprecision

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = n-1; i >= 0; --i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define rrep1(i,n) for(int i = (n); i >= 1; --i)
#define REP(i,n,m) for(int i = (n); i < (m); ++i)
#define all(vec) (vec).begin(),(vec).end()

#define debug(vec) for(auto v : vec) cerr << v << " "; cerr << endl;
#define debug2D(vec2D) for(auto vec : vec2D) { for (auto v : vec) cerr << v << " "; cerr << endl; } 
#define debugP(vec) for(auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl;
#define debug2DP(vec2D) for(auto vec : vec2D) { for (auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl; } 

const char en = '\n';

typedef long long ll;

constexpr ll INF = 1000000000; //10^10
//const ll MOD = 998244353;
constexpr ll MOD = 1000000007;

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

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

  ll n,m; cin >> n >> m;

  cout << n*m << endl;
}


Measured memory_bytes: 3648
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <string>
#include <complex>
#include <functional>
using namespace std;
typedef pair<int,int> P;
double dat[100][100];
int dp[1000001];//動的計画法
int prime[1000001];
int main(){
    int l;
    int m[12],n[12];
    while(cin>>l,l){
        int mn=0,ch=0;
        for(int i=0;i<12;i++){
            cin>>m[i]>>n[i];
        }
        for(int i=0;i<12;i++){
            mn+=(m[i]-n[i]);
            if(mn>=l){
                cout<<i+1<<endl;
                ch++;
                break;
            }
        }
        if(ch==0) cout<<"NA"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3060
D, G = map(int, input().split())
p = [0 for i in range(D)]
c = [0 for i in range(D)]
for i in range(D):
    p[i], c[i] = map(int, input().split())

def dfs(s):
    if len(s) == D:
        ans = 1000
        score = 0
        times = 0
        for i in range(D):
            if s[i] == "1":
                score += 100 * (i+1) * p[i] + c[i]
                times += p[i]
        if score >= G:
            ans = min(ans, times)
        else:
            idx = s.rfind("0")
            for i in range(1, p[idx]):
                if score + 100 * (idx+1) * i >= G:
                    ans = min(ans, times+i)
                    break
        return ans
    return min(dfs(s + "0"), dfs(s+ "1"))


print(dfs(""))

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

using ll = long long;

int main() {
    ll N, k;
    cin >> N >> k;
    ll pos = 0;
    ll mv = (pos/k + 1);
    for(int i=1; i<N; ++i) {
        pos += mv;
        while(pos/k + 1 > mv){
            ll tmp = pos;
            pos -= mv;
            mv = tmp/k + 1;
            pos += mv;
        }
    }
    cout << pos << endl;
}


Measured memory_bytes: 3116
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

int main()
{
	int w, n, cp, amd[30] = {0}, yoko[2];
	
	cin >> w >> n;

	for(int i = 1; i <= w; i++)
		amd[i-1] = i;

	for(int i = 0; i < n; i++){
		scanf("%d,%d", &yoko[0], &yoko[1]);

		cp = amd[yoko[0]-1];
		amd[yoko[0]-1] = amd[yoko[1]-1];
		amd[yoko[1]-1] = cp;
	}

	for(int i = 0; i < w; i++)
		cout << amd[i] << endl;
	
	return 0;
}

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

int main(void){
    
    int k;
    int n;
    int max=0;
    int j=0;
    cin >> k >> n;
    int a[n], m[n];
    for(int i=0;i<n;i++) {
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        if(i!=n-1) m[i] = a[i+1] - a[i];
        else m[i] = k - a[i] + a[0];
        
        if(m[i] > max) {
            max = m[i];
            j = i;
        }
    }
    
    int ans = 0;
    for(int i=0;i<n;i++){
        if(j != i) ans += m[i];
    }
    
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
typedef pair<int,int> pii;

long long MOD = 10000000000 + 7;

int main(){
  cout << setprecision(10);
  string S;
  cin >> S;
  map<char,int> m;
  m['a'] = 0;
  m['b'] = 0;
  m['c'] = 0;

  for(auto s: S){
    m[s] = 1;
  }
  bool flg = true;
  for(auto x: m){
    if(x.second == 0){
      flg = false;
      break;
    }
  }
  cout << (flg ? "Yes" : "No") << endl;
}


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

using namespace std;

#define REP(i, N) for (int (i) = 0; (i) < (N); ++(i))
#define READALL(c) for (auto &e : c) { cin >> e; }
#define PRINTALL(c) for (const auto &e : c) { cout << e << "\t"; } cout << "\n";

template <typename T>
using V = vector<T>;

typedef long double ld;

int main() {

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

	int N, M;
	cin >> N >> M;

	map<int, int> times;
	for (int i = 0; i < M; ++i) {
		int u, v;
		cin >> u >> v;
		times[u]++;
		times[v]++;
	}

	for (const auto& kv : times) {
		if (kv.second%2) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	
}

Measured memory_bytes: 4352
n = gets.to_i
work = []
n.times{|i|
  work[i] = gets.split(" ").map{|k|k.to_i}
  }
work.sort!{ |a, b| a[1] <=> b[1] }
sum = 0
flag = 0
n.times{|i|
  sum += work[i][0]
  if sum > work[i][1] then
    puts "No"
    flag = 1
    break
  end
  }
 if flag == 0 then
  puts "Yes"
 end

Measured memory_bytes: 18296
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			String s = scanner.next(), t = scanner.next();
			StringBuilder sb = new StringBuilder();
			for (char c : t.toCharArray()) {
				sb.append("[").append(c).append("\\?]");
			}
			Matcher matcher = Pattern.compile(sb.toString()).matcher(s);
			int index = -1;
			while (matcher.find(index + 1)) {
				index = matcher.start();
			}
			if (index >= 0) {
				System.out
						.println((s.substring(0, index) + t + s.substring(index + t.length())).replaceAll("\\?", "a"));
			} else {
				System.out.println("UNRESTORABLE");
			}
		}
	}
}


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

/*
d/sで時間は求まるが, int型でd/sを計算すると整数を返すので, 例えばd/sの答えが2.5でtが2だったとき,
d/s=2と変換され2<=2で条件を満たしてしまう. (本当は2.5<=2の形になるので満たさない)
pythonならd/sの答えを小数点込みで保持してくれるので正しい答えになる.
c++での方法として, d/s=tの式をd=tsの形に変換することで小数を避け正しい答えを得ることができる.
*/

int main() {
  int d, t, s;
  cin >> d >> t >> s;
  cout << (d <= (t * s) ? "Yes" : "No") << endl;
}


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

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
    ll N,K,d,a;
    cin>>N>>K;
    vector<ll> A(N);
    rep(i,K){
        cin>>d;
        rep(j,d){
            cin>>a;
            --a;
            ++A[a];
        }
    }

    ll ans = 0;
    rep(i,N){
        if(A[i]==0){
            ++ans;
        }
    }

    cout<<ans<<"\n";



	
	return 0;
}

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

int main() {
	int x;
	cin >> x;
	double a;
	string b;
	double ans=0;
	
	while (x--) {
		cin >> a >> b;
		if (b == "JPY") {
			ans += a;
		}
		else {
			ans += a*380000;
		}

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



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <iomanip>
#include <sstream>

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 1LL << 60;
const int inf = 1 << 30;

int even[100001];
int odd[100001];

int main() {
    int N; cin >> N;
    vector<int> V(N);
    for (int i = 0; i < N; ++i) {
        cin >> V[i];

        if (i & 1) ++odd[V[i]];
        else ++even[V[i]];
    }

    int ie = (max_element(even, even + 100001) - even);
    int io = (max_element(odd, odd + 100001) - odd);

    if (ie != io) {
        cout << (N - even[ie] - odd[io]) << endl;
    }
    else {
        int ce = even[ie], co = odd[io];
        even[ie] = odd[io] = 0;
        int ce2 = *max_element(even, even + 100001);
        int co2 = *max_element(odd, odd + 100001);
        cout << (N + min(-ce - co2, -ce2 - co)) << endl;
    }
    
    return 0;
}

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

struct query {
  int l, r, idx;
};

template<typename T>
class fenwick_tree {
  private:
    int n;
    vector<T> fenw;
  public:
    fenwick_tree(int _n) : n(_n) {
      fenw.resize(n);
    }

    size_t size() {
      return n;
    }

    void update(int x, T val) {
      while (x < n) {
        fenw[x] += val;
        x |= (x + 1);
      }
    }

    T query(int x) {
      T ans = 0;
      while (x >= 0) {
        ans += fenw[x];
        x = (x & (x + 1)) - 1;
      }
      return ans;
    }
};

int n, q;
vector<int> a;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<query> queries(q);
  for (int i = 0; i < q; i++) {
    queries[i].idx = i;
    cin >> queries[i].l >> queries[i].r;
    queries[i].l--; queries[i].r--;
  }
  sort(queries.begin(), queries.end(), [](const query &a, const query &b) {
    return a.r < b.r;
  });
  fenwick_tree<int> fenw(n + 1);
  vector<int> last(n + 1, -1);
  vector<int> ans(q);
  int j = 0;
  for (int i = 0; i < n; i++) {
    if (last[a[i]] != -1) {
      fenw.update(last[a[i]] + 1, -1);
    }
    last[a[i]] = i;
    fenw.update(i + 1, +1);
    while (j < q && queries[j].r == i) {
      ans[queries[j].idx] = fenw.query(queries[j].r + 1) - fenw.query(queries[j].l);
      j++;
    }
  }
  for (auto& x : ans) {
    cout << x << '\n';
  }
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;

const ll e5 = 1 << 21;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 62;

ll h,w;
string s[e3];
ll vis[e3][e3];
queue<vl> q;

int main(){
  cin >> h >> w;
  for(ll i = 0;i < h;i++) cin >> s[i];
  q.push(vl({0,0,1}));
  while(!q.empty()){
    ll x = q.front()[0];
    ll y = q.front()[1];
    ll c = q.front()[2];
    q.pop();
    if(vis[x][y]) continue;
    vis[x][y] = c;
    if(x-1 >= 0 && s[x-1][y] == '.') q.push(vl({x-1,y,c+1}));
    if(y-1 >= 0 && s[x][y-1] == '.') q.push(vl({x,y-1,c+1}));
    if(x+1 < h && s[x+1][y] == '.') q.push(vl({x+1,y,c+1}));
    if(y+1 < w && s[x][y+1] == '.') q.push(vl({x,y+1,c+1}));

  }
  if(vis[h-1][w-1] == 0) cout << -1 << endl;
  else{
    ll ans = h*w-vis[h-1][w-1];
    for(ll i = 0;i < h;i++){
      for(ll j = 0;j < w;j++){
        if(s[i][j] == '#') ans--;
      }
    }
    cout << ans << endl;
  }


}


Measured memory_bytes: 2560
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int N, M, X, Y, temp;
    std::cin >> N >> M >> X >> Y;
    
    std::vector<int> x;
    for (int i=0; i<N; ++i) {
        std::cin >> temp;
        x.push_back(temp);
    }
    x.push_back(X);
    std::vector<int> y;
    for (int i=0; i<N; ++i) {
        std::cin >> temp;
        y.push_back(temp);
    }
    y.push_back(Y);
    
    if (*std::max_element(x.begin(), x.end()) >= *std::min_element(y.begin(), y.end())) {
        std::cout << "War" << std::endl;
    } else {
        std::cout << "No War" << std::endl;
    }
}

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

long long ans(string s, string t) {
    // a~zがsの何文字目に現れるか ※自動的に昇順に格納される
  vector<vector<int>> pq(26); 
  for (int i = 0; i < s.size(); i++) {
    pq.at(s.at(i) - 'a').push_back(i);
  }
  
  int loop; // s = 0を右端まで読んだ回数
  
  // tを左端から読んでいき，それがsの何文字目に現れる文字であるかに着目して考える
  char c; // 所望の文字t.at(j)
  int x = -1; // 今sの何文字目を読んでいるかを格納する変数
  int y; // 次に読むべき文字が何番目かを格納する変数
  bool can_solve = true; // 解があるかどうか
  for (int j = 0; j < t.size(); j++) {
    c = t.at(j);
    clog << x << endl;
    // 所望の文字であるc=t.at(j)が，今読んでいるsのx文字目よりも右で最初に現れるのはいつか
    // すなわち，sにcが現れる「番目」（pq.at(c - 'a')に昇順に格納）のうち，xより大きいもののうち最小のものは何か
    // それを与えるイテレータit
    auto it = upper_bound(pq.at(c - 'a').begin(), pq.at(c - 'a').end(), x);
    int index = it - pq.at(c-'a').begin();
    // x文字目より右で見つかったとき
    if (index < pq.at(c - 'a').size()) {
      x = pq.at(c - 'a').at(index);
      continue;
    }
    // sのx文字目より右にcが見つからないときは，sの左端にもどる
    loop++; // 周数を増やす
    x = -1;
    // 再チャレンジ
    it = upper_bound(pq.at(c - 'a').begin(), pq.at(c - 'a').end(), x);
    index = it - pq.at(c-'a').begin();
    // sのどこかでcが見つかったとき
    if (index < pq.at(c - 'a').size()) {
      x = pq.at(c - 'a').at(index);
    } else {
      // 左端から右端まで読んでも見つからないとき
      can_solve = false;
      break;
    }
    clog << loop << endl;
  }
  
  long long ans;
  if (!can_solve) {
    ans = -1;
  } else {
    ans = s.size() * loop + x + 1;
  }
  
  return ans;
}

int main() {
  string s, t;
  cin >> s >> t;
  
  cout << ans(s, t);
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
const int mod=1000000007;
const int INF=1e18;

int p[100005],q[100005],r[100005];
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    f(i,0,a)
        cin>>p[i];
    f(j,0,b)
        cin>>q[j];
    f(k,0,c)
        cin>>r[k];
    sort(&p[0],&p[a],greater <int> ());
    sort(&q[0],&q[b],greater <int> ());
    sort(&r[0],&r[c],greater <int> ());
    int i=0,j=0,k=0;
    a=x,b=y;
    p[a]=0;
    q[b]=0;
    r[c]=0;
    int ans=0;
    while(i+j+k!=x+y)
    {
        // cout<<i<<" "<<j<<" "<<k<<" "<<p[i]<<" "<<q[j]<<" "<<r[k]<<endl;
        if(p[i]>=q[j] && p[i]>=r[k] && i<a)
        {
            ans+=p[i];
            i++;
        }
        else if(q[j]>=r[k] && j<b)
        {
            ans+=q[j];
            j++;
        }
        else
        {
            ans+=r[k];
            k++;
        }
    }
    // cout<<i<<" "<<j<<" "<<k<<endl;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2560
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


fn main () {
    input! {
        n : i32,
    }
    let m = n / 3 as i32;
    println!("{}", m);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
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;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N,C;
    cin >>N>>C;
    vector<ll>imo(100005);
    map<Pi,bool>m;
    vector<tuple<ll,ll,ll>>tp(N);
    rep(i,N){
        ll s,t,c;
        cin>>s>>t>>c;
        tp[i]=make_tuple(s,t,c);
        
    }
    sort(all(tp));
    rep(i,N){
        ll s,t,c;
        s=get<0>(tp[i]);
        t=get<1>(tp[i]);
        c=get<2>(tp[i]);
        if(m[mp(s,c)]==1){
            imo[s+1]++;
            imo[t+1]--;
        }else{
            imo[s]++;
            imo[t+1]--;
        }
        m[mp(t,c)]=1;
    }
    ll ans=0;
    rep(i,100003){
        imo[i+1]+=imo[i];
    }

    rep(i,100004){
        chmax(ans,imo[i]);
    }

    cout << ans << endl;


    return 0;
    

}

Measured memory_bytes: 18836
#include <cstdio>
using namespace std;

int main (void)
{
	int m, f, r, go;

	while (scanf("%d %d %d", &m, &f, &r)!= EOF && m!=-1 || f!=-1 || r!=-1){
		go = m+f;
		if (m == -1 || f == -1 || go < 30)
			printf("F\n");
		else{
			if (go >= 80)
				printf("A\n");
			else if (go >= 65)
				printf("B\n");
			else if (go >= 50)
				printf("C\n");
			else if (go >= 30){
				if (r >= 50)
					printf("C\n");
				else
					printf("D\n");
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1012
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const long long INF = 1e15;
using namespace std;


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

    vector<pair<long long, long long>> v(n);
    long long mini = INF, maxi = 0;
    long long rmax = 0, bmin = INF;
    rep(i,n){
        cin >> v[i].first >> v[i].second;
        if(v[i].first > v[i].second) swap(v[i].first, v[i].second); //R min, B max
        mini = min(v[i].first, mini); //r min
        maxi = max(v[i].second, maxi); //b max
        rmax = max(v[i].first, rmax);
        bmin = min(v[i].second, bmin);
    }
    long long ans = (rmax - mini) * (maxi - bmin);
    sort(all(v));

    long long rmin = INF;
    rep(i,n - 1){
        rmax = max(v[i].second, rmax); //i番目をbと交換する
        rmin = min(v[i].second, rmin);
        ans = min(ans, (rmax - min(rmin, v[i + 1].first))*(maxi - mini));
    }
    cout << ans << endl;
}


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

#define rep(i,begin,end) for(int i=begin;i<=end;i++)
#define repi(i,end,begin) for(int i=end;i>=begin;i--)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

#define MAXN 100001

int n,k;
int h[MAXN], dp[MAXN];

int sol(int pos){
	if(dp[pos] != -1) return dp[pos];

	if(pos == 1) return dp[pos] = 0;
	
	int ans = -1;

	if(pos <= k){
		rep(i,1,pos-1){
			if(ans == -1) ans = sol(i) + abs(h[pos]-h[i]);
			else ans = min(ans,sol(i) + abs(h[pos]-h[i]));
		}
	}
	else{
		rep(i,1,k){
			if(ans == -1) ans = sol(pos-i) + abs(h[pos]-h[pos-i]);
			else ans = min(ans,sol(pos-i) + abs(h[pos]-h[pos-i]));
		}
	}

	return dp[pos] = ans;
}

int main(){
fio

cin >> n >> k ;

memset(dp,-1,sizeof(dp));

rep(i,1,n) cin >> h[i];

cout << sol(n) << endl;
return 0;
}

Measured memory_bytes: 5760
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long n = sc.nextLong();
		long k = sc.nextLong();

		if(n == k) {
			System.out.println(0);
			return;
		}


		if(n>k) {
			long mod = n%k;
			long abs = Math.abs(mod-k);

			if(mod < abs) {
				System.out.println(mod);
			}else {
				System.out.println(abs);
			}
		}else{
			if(n < Math.abs(n-k)) {;
				System.out.println(n);
			}else{
				System.out.println(Math.abs(n-k));
			}
		}

	}
}


Measured memory_bytes: 23252
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AIZU
{
    class Program
    {
        static int cin() { return int.Parse(Console.ReadLine()); }
        static int cin(int D) {
            string s = Console.ReadLine();
            if (string.IsNullOrEmpty(s)) return D;
            return int.Parse(s);
        }
        static int[] cins() {
            string s = Console.ReadLine();
            if (string.IsNullOrEmpty(s)) return new int[] { };
            string[] ss = s.Split(' ');
            int[] Res = new int[ss.Length];
            for (int i = 0; i < ss.Length; i++) Res[i] = int.Parse(ss[i]);
            return Res;
        }
        static void print(object j) { Console.WriteLine(j.ToString()); }
        static void print(string j) { Console.WriteLine(j); }
        static void Main(string[] args)
        {
            int[] K = cins();
            int H = K[0], W = K[1];
            string[] SS = new string[H];
            for (int i = 0; i < H; i++)
                SS[i] = "#"+Console.ReadLine()+"#";
            print(new string('#',W+2));
            foreach (string s in SS) print(s);
            print(new string('#', W + 2));
            Console.ReadLine();
        }
    }
}


Measured memory_bytes: 13140
import collections

N, M = list(map(int, input().split()))

a = []
for i in range(N):
    tmp = list(map(int, input().split()))
    a += tmp[1:]

c = collections.Counter(a)
ans = 0
for val in c.values():
    if val == N:
        ans += 1

print(ans)


Measured memory_bytes: 3316
<?php

$n = trim(fgets(STDIN));
$arr = preg_split('/ /', trim(fgets(STDIN)));
$count = [];
$combi = [];
for ($i=1; $i <= $n; $i++) { 
    $count[$arr[$i-1]]++;
}
$sum = 0;
for ($i=1; $i <= $n; $i++) { 
    $sum += $combi[$i] = $count[$i] * ($count[$i]-1) / 2;
}
for ($i=1; $i <= $n; $i++) {
    print $sum - $combi[$arr[$i-1]] + ($count[$arr[$i-1]]-1) * ($count[$arr[$i-1]]-2) / 2 . "\n";
}


Measured memory_bytes: 87696
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

void _main() {
  int N, M;
  cin >> N >> M;
  vector<pair<int, int>> AB(N);
  rep(i, 0, N) {
    int a, b;
    cin >> a >> b;
    AB[i] = {a, b};
  }
  sort(AB.begin(), AB.end());

  ll ans = 0;
  rep(i, 0, N) {
    int  buy = min(M, AB[i].second);
    ans += (ll)buy * AB[i].first;
    M -= buy;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define endl "\n"
#endif
using namespace std;
typedef unsigned long long int lu;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> v;
typedef vector<lu> vu;
typedef vector<v> vv;
typedef vector<vu> vvu;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef pair<ll, ll> pll;
typedef vector<set<ll>> vsll;
typedef set<pair<ll, ll>> spll;
typedef vector<spll> vspll;
typedef vector<pll> vpll;
typedef pair<lu, lu> puu;
typedef vector<puu> vpuu;
const ll MOD = 1000000007;
const ld PI = 2 * acos(0.0);
const v dx = {1, -1, 0, 0};
const v dy = {0, 0, 1, -1};
#define round(x, y) ((x + y - 1) / y)
#define ce(x, y) ((x + y - 1) / y)
#define amax(x, y) \
    if (y > x)     \
        x = y;
#define amin(x, y) \
    if (y < x)     \
        x = y;
#define lcm(x, y) ((x) * (y) / __gcd(x, y))
#define sz(x) (ll) x.size()
#define sq(x) ((x) * (x))
#define cb(x) ((x) * (x) * (x))
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define yesno(f) \
    if (f)       \
        yes else no;
#define noo \
    { no return; }

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

template <typename T = ll>
vector<T> ga(ll n, bool oneIndexed = false) {
    vector<T> a = vector<T>(n + oneIndexed);

    for (ll i = 0; i < n; i++) {
        T p;
        cin >> p;
        a[i + oneIndexed] = p;
    }

    return move(a);
}

template <typename T, typename A>
void pa(vector<T, A> const &a, ll begin = 0, ll end = -1) {
    if (end == -1)
        end = sz(a) - 1;
    for (ll i = begin; i <= end; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}
#define MAX (ll)3e5
vv dp(1e5 + 1, v(2, 0));
void dfs(vv &adjList, ll curr, ll prev) {
    dp[curr][0] = 1;
    dp[curr][1] = 1;

    for (auto neigh : adjList[curr]) {
        if (neigh == prev)
            continue;
        dfs(adjList, neigh, curr);
        // the only way to paint the root black is to paint its chidlren white
        dp[curr][0] *= dp[neigh][1];
        // otherwise it's baap ka raj
        dp[curr][1] *= (dp[neigh][0] + dp[neigh][1]);
        dp[curr][0] %= MOD;
        dp[curr][1] %= MOD;
    }
}

void solve() {
    ll n;
    cin >> n;
    ll m = n - 1;
    vv adjList(n + 1, v(0));
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
    dfs(adjList, 1, -1);

    cout << (dp[1][0] + dp[1][1]) % MOD;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("file", "r", stdin);
    // freopen("file", "w", stdout);
    // ll t;cin >> t;while(t--)
    solve();
    return 0;
}

Measured memory_bytes: 18176
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()



int main()
{
  string a, b;
  cin >> a >> b;
  int ans = 0;
  for(int i = 0 ; i < 3 ; i++)
    ans += a[i] == b[i];
  cout << ans << endl;
  return 0;
}


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N;
    Scd(N);

    int x;
    vll a(N);
    Rep(i,N){
        Scd(x);
        a[i] = {x,i};
    }

    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());

    vector<vl> dp(N+1,vl(N+1,0));

    Rep(ni,N){
        Rep(ki,N){
            int ai = ni-ki;
            if( ai < 0 ) break;
            int bi = ki;
            dp[ai+1][bi] = max( dp[ai+1][bi],
                    dp[ai][bi] + a[ni].first*abs(a[ni].second-ai) );
            dp[ai][bi+1] = max( dp[ai][bi+1],
                    dp[ai][bi] + a[ni].first*abs(a[ni].second-(N-bi-1)) );
        }
    }

    ll ans = 0;
    Rep(i,N+1){
        ans = max( ans, dp[i][N-i] );
    }

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

    return 0;
}



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

int main(){
  char a;
  char b[10];
  int c = 0;
  int count = 0;
  bool ans = true;
  while(cin >> a){
    b[c] = a;
    c++;
  }
  if(b[0] != 'A'){
    cout << "WA" << endl;
    ans = false;
  }else if(b[1] >= 'A' && b[1] <= 'Z'){
    cout << "WA" << endl;
    ans = false;
  }else if(b[c-1] >= 'A' && b[c-1] <= 'Z'){
    cout << "WA" << endl;
    ans = false;
  }else{
    for(int i = 2;i < c-1;i++){
      if(b[i] == 'C'){
        count++;
      }
      if(b[i] >= 'A' && b[i] <= 'Z' && b[i] != 'C'){
        cout << "WA" <<endl;
        ans = false;
      }else if(count == 2){
        cout << "WA" << endl;
        ans = false;
      }else if(i == c-2 && count == 0){
        cout << "WA" << endl;
        ans = false;
      }
    }
  }

  if(ans){
    cout << "AC" << endl;
  }
}


Measured memory_bytes: 256
def inpl(): return [int(i) for i in input().split()]
import sys
import numpy 
N = int(input())
A = numpy.array([inpl() for _ in range(N)])
ans = 0
for i in range(N):
    A[i][i] = 10**9+1
for i in range(N):
    for j in range(i):
        mindis = numpy.min(A[i] + A[j])
        if mindis > A[i][j]:
            ans += A[i][j]
            continue
        if mindis < A[i][j]:
            print(-1)
            sys.exit()
print(ans)

Measured memory_bytes: 16268
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#define endl "\n"
using namespace std;

int main()
{
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;

    cout << "A" << s2[0] << "C" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
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; }



int main(int argc, char const *argv[]) {
  int n;
  cin >> n;
  if(n%1000==0) cout << "0" << endl;
  else cout << 1000-n%1000 << endl;
  return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned ui;
typedef unsigned long long ul;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<bool, bool> pbb;
typedef vector<int> vi;
#define pb push_back
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define ls (i << 1)
#define rs (i << 1 | 1)
#define enum(i, j, k) for(int i = j; i <= (k); i ++)
#define open(i, j, k) for(int i = j; i <  (k); i ++)
#define dec(i, j, k)  for(int i = j; i >= (k); i --)
#define ae(x) for(node *p = h[x]; p; p = p->nxt)
#define fill(x, k) memset(x, k, sizeof x)
#define copy(x, y) memcpy(x, y, sizeof x)
#define fio(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
template <class T> bool chkmin(T &x, T y)
{ return y < x ? (x = y , true) : false; }
template <class T> bool chkmax(T &x, T y)
{ return y > x ? (x = y , true) : false; }
void __init()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(16);
    srand(time(0) ^ ui(ul(new char)));
}
/* default code ends here */
#define maxn 100100
int n;
int l[maxn], r[maxn];
int main()
{
    __init();
    cin >> n;
    enum(i, 1, n)
        cin >> l[i] >> r[i];
    sort(l, l + n + 1, greater<int>());
    sort(r, r + n + 1);
    ll ans = 0;
    for(int i = 0; l[i] > r[i]; i ++)
        ans += l[i] - r[i];
    cout << 2 * ans << endl;
    return 0;
}

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


int main() {
  int s, w;
  cin >> s >> w;
  string ans = "safe";
  if(s <= w) ans = "unsafe";
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3592
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << (#x) << ": " << (x) << endl
#define DEBUG_VEC(v)            \
    cerr << #v << ": ";         \
    REP(__i, (v).size())        \
    cerr << ((v)[__i]) << ", "; \
    cerr << endl

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main()
{
    ios::sync_with_stdio(false);

    int A, B, C;
    cin >> A >> B >> C;
    cout << min(C, B / A);
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <vector>
#include <cstring>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
ll MAX(ll a,ll b,ll c){return max(a,max(b,c));}
ll MIN(ll a,ll b,ll c){return min(a,min(b,c));}
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
template<class T> inline bool chmax(T &a,T& b){if(a < b){a = b; return true;} else return false;}
template<class T> inline bool chmin(T &a,T& b){if(a > b){a = b; return true;} else return false;}
ll INF = 2000000000000;
int main(void){
    int h,w;
    cin >> h >> w;
    rep(i,h+2){
        if(i == 0 || i == h+1) rep(j,w+2) cout << '#';
        else{
            string s;
            cin >> s;
            cout << '#' << s << '#';
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,ri,le;
struct node{
	int l,r;
}a[1000005];
int tot;
char s[1000005];
int cmp(node a,node b){
	return a.l-a.r>b.l-b.r;
}
int main(){
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		int l=0,r=0;
		scanf("%s",s+1);
		for(j=1;s[j];j++)
			if(s[j]=='(')l++;
			else if(s[j]==')'){
				if(l)l--;
				else r++;
			}
		if(!l&&r)ri+=r;
		else if(l&&!r)le+=l;
		else if(l&&r)a[++tot]=(node){l,r};	
	}
	sort(a+1,a+1+tot,cmp);
	for(int i=1;i<=tot;i++){
		if(le<a[i].r)
			return puts("No"),0;
		//le-=a[i].y-a[i].x;
		le-=a[i].r,le+=a[i].l;
	}
	if(le!=ri)puts("No");
	else puts("Yes");
	return 0;
}

Measured memory_bytes: 5256
import math
a, b, h, m = map(int, input().split())
t = 60*h+m
a_angl = (t%720) / 2
b_angl = (t%60) * 6

ans = math.sqrt(a**2 + b**2 - 2*a*b*math.cos(math.radians(abs(a_angl-b_angl))))
print(ans)

Measured memory_bytes: 62180
#include <iostream>
#include<algorithm>
using namespace std;
int n;
int a[100000+5],b[2];
unsigned long long sum=0;
unsigned long long sums=0;
int main(){
    scanf("%d",&n);
    if(n==1){
        cout<<"0\n";
        return 0;
    }

    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    int l=1,r=n-1;

    sum=abs(a[0]-a[n-1])+abs(a[0]-a[n-2]);
    b[0]=a[n-1];b[1]=a[n-2];
    bool f=0;//jiang yao fang min
    while(r-2>=l){
        if(f){
            sum+=max(abs(a[r]-b[0])+abs(a[r-1]-b[1]),abs(a[r-1]-b[0])+abs(a[r]-b[1]));
            b[0]=a[r]; b[1]=a[r-1];
            l+=2;

        }
        else{
            sum+=max(abs(a[l]-b[0])+abs(a[l+1]-b[1]),abs(a[l+1]-b[0])+abs(a[l]-b[1]));
            b[0]=a[l]; b[1]=a[l+1];
            r-=2;
        }
            f=1-f;

    }
    l=0,r=n-2;
    f=1;
    sums=abs(a[n-1]-a[0])+abs(a[n-1]-a[1]);
    b[0]=a[0];b[1]=a[1];
    while(r-2>=l){
        if(f){
            sums+=max(abs(a[r]-b[0])+abs(a[r-1]-b[1]),abs(a[r-1]-b[0])+abs(a[r]-b[1]));
            b[0]=a[r]; b[1]=a[r-1];
            l+=2;

        }
        else{
            sums+=max(abs(a[l]-b[0])+abs(a[l+1]-b[1]),abs(a[l+1]-b[0])+abs(a[l]-b[1]));
            b[0]=a[l]; b[1]=a[l+1];
            r-=2;
        }
            f=1-f;

    }
    cout<<max(sums,sum)<<'\n';


}//6 3 1 4 1 5 9
//1 1 3 4 5 9
//    1 9 1 5 3
//2+6+8+5+5+3


Measured memory_bytes: 640
///بِسْمِ الّٰلهِ الرَّحْمٰنِ الرَحِيْمِ
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi acos(-1.0)
int main()
{
     ios_base::sync_with_stdio(false);cin.tie(NULL);
     ll int i,n,t,j=0,p,x,a=0,b,l=0,r=0,y,k,c,sum=0,m,d;
     string s;
     cin>>s;

     for(i=0;i<s.size();i++){
        if( s[i]=='?'){
            s[i]='D';
            }
     }
     cout<<s<<endl;
     return EXIT_SUCCESS;
}




Measured memory_bytes: 3772
#include <iostream>
#include <string>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
// �`�b�̉��̂v�`���O�ɒu������������i���s�j
 /* int A;
    for(int i=0;i<M;i++){
    if(S[i]=="AC"){
      A=p[i];
      for(int j=i+1;p[j]==A;j++)
	S[j]="0";
    }
    }
  int countA=0, countW=0;
  for(int i=0;i<M;i++){
    if(S[i]=="AC")
      countA++;
    else if(S[i]=="WA")
      countW++;
      
      }*/
int main(void){

  int N,M;
  cin >> N >> M;
  int p[M];
  string S[M];
  int j=1,countA=0,countW=0,count=0,arr[N];
  for(int i=1;i<N+1;i++)
    arr[i]=0;
  for(int i=0;i<M;i++)
    cin >>p[i] >>S[i];
  map <int,int> m;
 
  rep(i,M){
    if(m[p[i]]<1){
      if(S[i]=="WA")
	arr[p[i]]++;
      else if(S[i]=="AC"){
	countA++;
 	countW+=arr[p[i]];
 	m[p[i]]++;
      }

     }
    
   }

 
 
   cout << countA << " " << countW <<endl;

   return 0;
 }


Measured memory_bytes: 11136
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
	int n, l;
	while(cin >> n >> l) {
		if(n == 0 && l == 0) break;

		vector<char> dir(n);
		vector<int> p(n);
		rep(i, n) {
			cin >> dir[i] >> p[i];
		}

		int cnt = 0, id = -1, next[105];
		bool used[25];
		memset(used, 0, sizeof(used));

		while(true) {
			memset(next, 0, sizeof(next));

			rep(i, n) {
				if(used[i]) continue;
				if(dir[i] == 'R') p[i]++;
				else p[i]--;

				next[p[i]]++;
			}

			rep(i, n) {
				if(used[i]) continue;
				if(next[p[i]] == 2) {
					dir[i] = (dir[i] == 'R' ? 'L' : 'R');
				}
			}

			rep(i, n) {
				if(used[i]) continue;
				if(p[i] == l) {
					used[i] = true;
					id = i;
				}
			}

			rep(i, n) {
				if(used[i]) continue;
				if(p[i] == 0) {
					used[i] = true;
					id = i;
				}
			}

			bool flag = true;
			rep(i, n) {
				if(used[i]) continue;
				flag = false;
			}

			if(flag) break;
			cnt++;
		}

		cout << cnt + 1 << " " << id + 1 << endl;
	}

	return 0;
}

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

int main(){
    int h,w;

    while(1){
        cin >> h >> w;
        if(h==0 && w==0) break;
        else{
          for(int i=0; i<h; i++){
            cout << '#';
            for(int j=0; j<w-2; j++){
                if(i==0 || i==h-1){
                    cout << '#';
                }
                else{
                    cout << '.';
                }
            }
            cout << '#' << endl;
          }
        }
      cout << endl;
    }
}


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
	int N, M;
	cin >> N >> M;

	int cnt[10];
	rep(i, 10) cnt[i] = 0;

	if (N == 1 && M == 1) cnt[1] = 1;
	else if (N == 1) {
		cnt[2] = 2;
		cnt[3] = M - 2;
	} else if (M == 1) {
		cnt[2] = 2;
		cnt[3] = N - 2;
	} else {
		cnt[4] = 4;
		cnt[6] = 2 * ((N - 2) + (M - 2));
		cnt[9] = (N - 2) * (M - 2);;
	}

	cout << cnt[1] + cnt[3] + cnt[5] + cnt[7] + cnt[9] << endl;

    return 0;
}


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

int main()
{
  int a,b,c,d;
  cin>> a;
  cin >>b;
  cin>>c;
  d=(a*b);
  if(d<c) 
  {
  cout <<d<<endl;
  }
  else
  {
  cout << c<<endl;
  }
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional>
#include <cmath>
#include <numeric>
#include <bitset>
#include <cstdint>
using namespace std;

#ifdef DEBUG
#include <cassert>
#else
#define assert(x)
#endif

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

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

int main()
{
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // 浮動小数の表示の精度
    cout << setprecision(15);

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

    if (p == 2 || p == 5)
    {
        ll ans = 0;
        rep(i, s.size())
        {
            if ((s[i] - '0') % p == 0)
            {
                ans += i + 1;
            }
        }
        cout << ans << endl;
        return 0;
    }

    vector<int> cnt(p), powten(p - 1);
    cnt[0] = 1;
    powten[0] = 1;
    rep(i, p - 2)
    {
        powten[i + 1] = powten[i] * 10 % p;
    }
    int cur = 0;
    for (int i = n - 1; i >= 0; --i)
    {
        int c = s[i] - '0';
        cur = cur + c * powten[(n - 1 - i) % (p - 1)];
        cur %= p;
        ++cnt[cur];
    }

    ll ans = 0;
    rep(i, p)
    {
        ll k = cnt[i];
        ans += k * (k - 1) / 2;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for(auto v:(V))cout<<v<<" "<<endl
inline int GCD(int a, int b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;

int kiriage(int x)
{
    if (x % 10 == 0)
    {
        return x;
    }
    else
    {
        return x + (10 - (x % 10));
    }
}

int main()
{
    vi A(5);
    vi amari(5);
    int mina = 9;
    int mina_index = 0;
    rep(i, 5)
    {
        cin >> A[i];
        amari[i] = A[i] % 10;
        if (0 < amari[i] && amari[i] < mina)
        {
            mina = amari[i];
            mina_index = i;
        }
    }
    int ans = 0;
    rep(i, 5)
    {
        if (i == mina_index)
        {
            ans += A[i];
        }
        else
        {
            ans += kiriage(A[i]);
        }
    }
    cout << ans << endl;
}

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 444;
const LL mod = 1e9 + 7;
int N;
int a[MC];
int b[MC];
LL dp[MC][MC][2];
LL f[MC][MC];
bool ba[MC],bb[MC];

int main(){
	cin >> N;
	repp(i,0,N) cin >> a[i];
	repp(i,0,N) cin >> b[i];
	LL mix = 1;
	repm(i,N,0) if(i%3>0) mix = mix * i % mod;
	repm(i,N-1,-1){
		LL z = 0;
		repm(j,N-1,-1){
			dp[i][j][0] = (i+1==N?0:dp[i+1][j][0])+z;
			if(i<N-1&&a[i+1]==b[j]) ++z;
		}
	}
	repp(i,0,N){
		fill(ba,ba+MC,0);
		bb[a[i]] = 1;
		repp(j,0,N){
			ba[b[j]] = 1;
			if(ba[a[i]]||bb[b[j]]) dp[i][j][0] = 0;
			f[i][j] = dp[i][j][0];
		}
	}
	repp(k,1,N/3){
		repp(i,0,N){
			repm(j,N-1,0){
				(dp[i][j-1][(k-1)%2] += dp[i][j][(k-1)%2]) %= mod;
			}
		}
		repp(j,0,N){
			repm(i,N-1,0){
				(dp[i-1][j][(k-1)%2] += dp[i][j][(k-1)%2]) %= mod;
			}
		}
		repp(i,0,N){
			repp(j,0,N){
				dp[i][j][k%2] = max((LL)0,f[i][j] - k * 3) * dp[i+1][j+1][(k-1)%2];
			}
		}
	}
	cout << dp[0][0][(N/3-1)%2] * mix % mod << endl;
	return 0;
}


Measured memory_bytes: 4352
def popcount(x):
    return bin(x).count("1")

N, X = open(0).read().split()
N = int(N)
XS = list(X)
X = int(X, 2)

p = popcount(X)
xi = X % (p + 1)
if p == 1:
    xd = 0
else:
    xd = X % (p - 1)

for i in range(N):
    if XS[i] == "1":
        if p == 1:
            print(0)
            continue
        else:
            k = pow(2, N - 1 - i, p - 1)
            x = (xd - k) % (p - 1)
    else:
        k = pow(2, N - 1 - i, p + 1)
        x = (xi + k) % (p + 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)


Measured memory_bytes: 10892