akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};
 
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; }
 
struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};




signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Timer TM;

    ll n,k,r,s,p;
    string t;
    cin>>n>>k>>r>>s>>p>>t;
    ll dp[200010][5];
    rep(i,200010)rep(j,5) dp[i][j]=0;
    ll ans=0;
    ll h[300010]={};
    rep(i,n){
        if(t[i]=='r'){
            if(h[i]!=3){
                h[i+k]=3;
                ans+=p;
            }
        }
        else if(t[i]=='s'){
            if(h[i]!=1){
                h[i+k]=1;
                ans+=r;
            }
        }
        else{
            if(h[i]!=2){
                h[i+k]=2;
                ans+=s;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2816
#include<stdio.h>

int main(void){
  int n,k;
  int i;
  int ans;
  scanf("%d %d",&n,&k);
  ans=k;
  for(i=0;i<(n-1);i++){
    ans*=(k-1);
  }
  printf("%d\n",ans);
  return 0;
}


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

int main(){
    ll n, k, ans;
    ans = 0;
    cin >> n >> k;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    sort(h.begin(), h.end());
    reverse(h.begin(), h.end());
    for (int i = k; i < n; i++){
        ans += h[i];
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
using lint = long long;
#define low lower_bound
#define upp upper_bound
#define rep(i, n) for (lint i = 0; i < lint(n); ++i)
#define Rep(i, n) for (lint i = lint(n); i >= 0; --i)
#define all(vec) (vec).begin(), (vec).end()
#define cend printf("\n");
#define prique(T) priority_queue<T, vector<T>, greater<T>>
#define prique2(T) priority_queue<T>

struct edge { int to; double cost; };
using P = pair<lint, lint>;
using D = pair<double, double>;
using DI = pair<double, int>;
//const lint mod = 998244353LL;
const lint mod = 1000000007LL;
const lint inf = 3LL * mod * mod;

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

lint modpow(lint x, lint n, lint m) {
	lint ans = 1;
	while (n > 0) {
		if (n & 1) {
			ans *= x;
			if (m <= ans) ans %= m;
		}
		x *= x;
		if (m <= x) x %= m;
		n >>= 1;
	}
	return ans;
}

lint fact[1000000];
void f_init(lint n) {
	if (1000000 <= n) return;
	fact[0] = fact[1] = 1;
	for (lint i = 2; i <= n; ++i) {
		fact[i] = i * fact[i - 1];
		if (mod <= fact[i]) fact[i] %= mod;
	}
	return;
}

lint inver[1000000]; bool inve[100000];
lint inv(lint x) {
	if (x == 0) return 0;
	else if (inve[x]) return inver[x];
	else {
		inve[x] = true;
		return inver[x] = modpow(x, mod - 2, mod);
	}
}

lint comb(lint n, lint r) {
	if (n < r) return 0;
	if (n == r) return 1;
	lint ans = fact[n] * inv(fact[n - r]) % mod * inv(fact[r]) % mod;
	if (ans < 0) return ans + mod;
	return ans;
}

lint nck[1010][1010];
void comb(lint n) {
	rep(i, n + 1) {
		rep(j, i + 1) {
			if (j == 0 || i == j) nck[i][j] = 1;
			else nck[i][j] = nck[i - 1][j - 1] + nck[i - 1][j];
		}
	}
}

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

lint lcm(lint a, lint b) { return a / gcd(a, b) * b; }

bool pri(lint p) {
	for (lint i = 2; i * i <= p; i == 2 ? ++i : i += 2) if (p % i == 0) return false;
	return p > 1;
}

map<lint, lint> factring(lint n) {
	map<lint, lint>ans;
	for (lint i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			n /= i;
			++ans[i];
		}
	}
	if (n != 1) ++ans[n];
	return ans;
}

double dis(D a, D b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)); }

int n, c;
vector<int>g[100010];
int ans[100010];
bool used[100010];
queue<P>que;
map<P, int>mp;
int main() {
	cin >> n;
	rep(i, n - 1) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].push_back(b);
		g[b].push_back(a);
		mp[P(a, b)] = i + 1;
	}
	used[0] = true;
	que.push(P(0, 0));
	while (!que.empty()) {
		P p = que.front(); que.pop();
		int v = p.first;
		int c1 = p.second, c2 = 1;
		rep(i, g[v].size()) {
			if (used[g[v][i]]) continue;
			used[g[v][i]] = true;
			if (c2 == c1) ++c2;
			c = max(c, c2);
			ans[mp[P(v,g[v][i])]] = c2;
			que.push(P(g[v][i], c2));
			++c2;
		}
	}
	cout << c << endl;
	rep(i, n - 1) {
		cout << ans[i + 1] << endl;
	}
}

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

#define pb push_back
#define fst first
#define snd second
#define ALL(s) s.begin(),s.end()
#define fill(a,c) memset(&a, c, sizeof(a))
#define fore(i,x,y) for(ll i=x;i<y;i++)
#define SZ(x) ((int)(x).size())
#define PI acos(-1)
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long ll;
using namespace std;

const int MAXN = 1e5+10;
vector<int> g[MAXN];
int n,m;
int tsort(){
    priority_queue<int> q;
    vector<int> d(2*n,0), dist(n,0);
    fore(i,0,n) fore(j,0,SZ(g[i]))d[g[i][j]]++;
    fore(i,0,n) if(!d[i])q.push(-i);
    while(SZ(q)){
        int x=-q.top(); q.pop();
        fore(i,0,SZ(g[x])){
            d[g[x][i]]--; dist[g[x][i]] = max(dist[g[x][i]],dist[x]+1);
            if(!d[g[x][i]]) q.push(-g[x][i]);
        }
    }
    int ans = 0;
    fore(i,0,n) ans = max(ans,dist[i]);
    return ans;
}

int main() {FIN;
    cin>>n>>m;
    fore(i,0,m){
        int u,v; cin>>u>>v; u--; v--;
        g[u].pb(v);
    }
    cout<<tsort()<<"\n";
    return 0;
}



Measured memory_bytes: 9748
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 2010

int n, a[SIZE];
int dp[SIZE][2];
int z,w;

int turn(int now, int p = 0){
  int res;
  res = p ? INF : 0;

  if(dp[now][p]) return dp[now][p];
  
  for(int i=now+1;i<n-1;i++){
    if(p == 0)
      res = max(res, turn(i, 1-p));
    else
      res = min(res, turn(i, 1-p));
  }

  if(p == 0){
    if(now == -1){
      res = max(res, abs(a[n-1] - w));
    }else{
      res = max(res, abs(a[n-1] - a[now]));
    }
  }else{
    res = min(res, abs(a[n-1] - a[now]));
  }

  return dp[now][p] = res;
}

int main(){
  scanf("%d%d%d",&n,&z,&w);

  for(int i=0;i<n;i++){
    scanf("%d",a+i);
  }

  cout << turn(-1) << endl;
  
  return 0;
}


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

int main() {
  vector<int> l, r{0};
  int N, K; cin >> N >> K;
  for (int i = 0; i < N; i++) {
    int x; cin >> x;
    if (x >= 0) r.push_back(x);
    else l.push_back(-x);
  }
  l.push_back(0);
  reverse(l.begin(), l.end());
  int res = 2e9;
  for (int i = 0; i < min<int>(K+1, l.size()); i++) {
    int j = K - i;
    if (j >= r.size()) continue;
    int L = l[i], R = r[j];
    res = min(res, L + R + min(L, R));
  }
  cout << res << endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  for (int i = 0; i < n; i++) {
    cin >> b.at(i);
  }

  ll sum_a = accumulate(a.begin(), a.end(), 0LL);
  ll sum_b = accumulate(b.begin(), b.end(), 0LL);
  if (sum_a < sum_b) {
    cout << -1 << endl;
    return 0;
  }
  bool flag = true;
  for (int i = 0; i < n; i++) {
    if (a.at(i) < b.at(i)) flag = false;
  }
  if (flag) {
    cout << 0 << endl;
    return 0;
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (a.at(i) < b.at(i)) ans++;
  }

  vector<int> d;
  for (int i = 0; i < n; i++) {
    if (a.at(i) > b.at(i)) {
      d.push_back(a.at(i) - b.at(i));
    }
  }
  sort(d.rbegin(), d.rend());

  vector<int> e;
  for (int i = 0; i < n; i++) {
    if (a.at(i) < b.at(i)) {
      e.push_back(b.at(i) - a.at(i));
    }
  }
  sort(e.rbegin(), e.rend());
  int cnt3 = 1;
  int k = 0;
  int pool = d.at(k);
  for (int i = 0; i < e.size(); i++) {
    while (pool < e.at(i)) {
      k++;
      pool += d.at(k);
      cnt3++;
    }
    pool -= e.at(i);
    cnt3++;
  }
  cout << cnt3 << endl;

}

Measured memory_bytes: 1660
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stdint.h>

const int64_t INF=1e15+7;

std::vector<std::pair<int64_t,int64_t> > delta[200005];

int64_t st[800005];
int64_t lazy[800005];

void push(int64_t w,int64_t L,int64_t R){
  if(R-L>1){
    lazy[w<<1]+=lazy[w];
    lazy[w<<1|1]+=lazy[w];
  }
  st[w]+=lazy[w];
  lazy[w]=0;
}

void pull(int64_t w,int64_t L,int64_t R){
  st[w]=std::max(st[w<<1],st[w<<1|1]);
}

void update(int64_t w,int64_t L,int64_t R,int64_t a,int64_t b,int64_t v){
  push(w,L,R);
  if(b<=L||a>=R) return;
  if(a<=L&&b>=R){
    lazy[w]+=v;
    push(w,L,R);
  }else{
    int64_t M=(L+R)/2;
    update(w<<1,L,M,a,b,v);
    update(w<<1|1,M,R,a,b,v);
    pull(w,L,R);
  }
}

int64_t query(int64_t w,int64_t L,int64_t R,int64_t a,int64_t b){
  push(w,L,R);
  if(b<=L||a>=R) return -INF;
  if(a<=L&&b>=R){
    return st[w];
  }else{
    int64_t M=(L+R)/2;
    return std::max(query(w<<1,L,M,a,b),
		    query(w<<1|1,M,R,a,b));
  }
}

int64_t dp[200005];

int main(){
  int64_t N,M;
  scanf("%ld %ld",&N,&M);
  for(int64_t i=0;i<M;i++){
    int64_t L,R,A;
    scanf("%ld %ld %ld",&L,&R,&A);
    delta[L].emplace_back(L,A);
    delta[R+1].emplace_back(L,-A);
  }
  for(int64_t i=1;i<=N+1;i++){
    for(auto p:delta[i]){
      update(1,0,N+1,0,p.first,p.second);
    }
    dp[i]=query(1,0,N+1,0,i);
    update(1,0,N+1,i,i+1,dp[i]);
  }
  printf("%ld\n",dp[N+1]);
  return 0;
}


Measured memory_bytes: 29440
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String N = (String) sc.nextLine();
		if (N.contains("7")) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 35632
import numpy as np
n, k = map(int, input().split())
M = 10**9 + 7

a = list(map(int, input().split()))

def s(n):
    return ((n + 1) * n) // 2

def calc_t(tk):
    tmp = a * tk
    t = [0] * n
    for i in range(n):
        ans = 0
        for j in range(i + 1, n * tk):
            if tmp[i] > tmp[j]:
                ans += 1
        t[i] = ans
    return np.array(t)

t1 = calc_t(1)
t2 = calc_t(2) - t1 * 2
print((int(sum(t1)) * s(k) + int(sum(t2)) * s(k - 1)) % M)


Measured memory_bytes: 14244
#include<iostream>
#include<cmath>
#include<climits>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int dp[n];
	for(int i=0;i<n;i++)
		dp[i]=INT_MAX;
	dp[0]=0;
	dp[1]=abs(a[1]-a[0]);
	for(int i=2;i<n;i++)
	{	if(k==1)
			dp[i]=abs(a[i]-a[i-1])+dp[i-1];
		for(int j=1;j<k && (i-j)>=1;j++)
		{
		int sub1=abs(a[i]-a[i-j]);
		int sub2=abs(a[i]-a[i-j-1]);
		int x=min(sub1+dp[i-j],sub2+dp[i-j-1]);
		if(x<dp[i])
			dp[i]=x;
		}
	}
		cout<<dp[n-1];
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
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; }
const ll INF=1LL<<60;
const int mod=1e9+7;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<ll> p(200001);
    int n;cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
        p[a[i]]++;
    }
    ll sum=0;
    for(int i=1;i<=200000;i++){
        sum+=p[i]*(p[i]-1)/2;
    }
    for(int i=0;i<n;i++){
        cout << sum-(p[a[i]]-1) << endl;
    }
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using ll = long long;
using  INT = long long;
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define ALL(x) x.begin(),x.end()

#define INF (int)1e9 //10^9:∞
#define LLINF (long long)1e12
#define MOD (int)1e9+7 //10^9+7:合同式の法
#define PI 3.141592653589

#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

#define Graph vector<vector<int>>
#define PII pair<int,int>
#define VI vector<int>
#define VVI vector<vector<int>>
#define VPII vector<pair<int,int>>

#define DDD fixed<<setprecision(10)

using namespace std;
/*........................................DEFINE FUNCTIONS.........................................*/


/*....................................DEFINE GLOBAL VARIABLES .....................................*/



/*.........................................kemkemG0................................................*/
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; cin >> n;
	vector<pair<int, int>> mp0(100005), mp1(100005); //first=value second=key
	REP(i, n) {
		int v;
		cin >> v;
		if (i % 2 == 0) {mp0[v].first++; mp0[v].second = v;}
		else {mp1[v].first++; mp1[v].second = v;}
	}
	int ans = n;
	
	sort(ALL(mp0), greater<PII>());
	sort(ALL(mp1), greater<PII>());

	int m0 = mp0[0].second, m1 = mp1[0].second;

	ans -= (mp0[0].first + mp1[0].first);

	if (m0 == m1) {
		int res,res1;
		res=res1=ans;

		res+=mp0[0].first -mp0[1].first;
		res1+=mp1[0].first -mp1[1].first;
		ans=min(res,res1);
	}
	cout << ans << endl;





	return 0;
}













Measured memory_bytes: 4740
N = int(input())
a = list(map(int,input().split()))

a_bin = [[] for _ in range(N)]
len_max = 0

odd_or_even = [0 for _ in range(30)]

for i in range(N):
    a_bin[i] = format(a[i],"030b")
    for j in range(30):
        odd_or_even[j] = (odd_or_even[j]+int(a_bin[i][j]))%2

x = [[0]*30 for _ in range(N)]

for i in range(30):
    if odd_or_even[i] == 1:
        for j in range(N):
            x[j][i] = (int(a_bin[j][i])+1)%2
    else:
        for j in range(N):
            x[j][i] = int(a_bin[j][i])

for j in range(N):
    temp = 0
    for i in range(30):
        temp += x[j][i]*(2**(29-i))
    print(temp)


Measured memory_bytes: 180088
#include <iostream>
#include <algorithm>
#include <cmath>
#include <list>
#include <queue>
#include <set>
#include <vector>

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define FORE(i,a,b) for (int i=(int)(a);i<=(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REPE(i,n) FOR(i,0,n)

typedef long long ll;

int main() {
  int N;
  cin >> N;
  priority_queue<double, vector<double>, greater<double>> V;
  REP(i,N) {
    double v;
    cin >> v;
    V.push(v);
  }

  REP(i,N-1) {
    double a,b;
    a = V.top();
    V.pop();
    b = V.top();
    V.pop();
    V.push((a+b)/2);
  }

  cout << V.top() << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L


int Z_algo(string s) {
    int n = s.length();
    vector<int> z(n);
    int L = 0, R = 0;
    for (int i = 1; i < n; i++) {
        if (i > R) {
            L = R = i;
            while (R < n && s[R - L] == s[R]) R++;
            z[i] = R - L; R--;
        }
        else {
            int k = i - L;
            if (z[k] < R-i + 1) z[i] = z[k];
            else {
                L = i;
                while (R < n && s[R - L] == s[R]) R++;
                z[i] = R - L; R--;
            }
        }
    }
    int mx = 0;
    for (int i = 0; i < n; i++) mx = max(mx, min(i,z[i]));
    return mx;
}

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int happy = 0;
    int two = 0;
    for (int i = 0; i < n-1; i++) {
        if (s[i] == s[i + 1] && s[i] == 'R') happy++;
        if (s.substr(i, 2) == "RL") two++;
    }
    for (int i = n - 1; i > 0; i--) {
        if (s[i] == 'L' && s[i] == s[i - 1]) happy++;
    }
    int tmp = k;
    k -= min(k, two);
    happy += (tmp - k) * 2;
    happy += k;
    cout << min(n - 1, happy);
    return 0;
}

Measured memory_bytes: 3744
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 1<<30
#define MOD 1000000007
#define mod 10007
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //------------------------------
    ll a,b;cin>>a>>b;
    //cout<<a/b<<" "<<a%b<<" "<<double(a/(double)b)<<endl;
    printf("%lld %lld %.8lf\n",a/b,a%b,(double)a/(double)b);
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------

































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

typedef long long int ll;

ll arr[100005];

int main()
{
	ll n;
	cin>>n;
	ll a[n],sum=0;
	for(ll i=0;i<n;i++)
	{
		cin>>a[i];
		arr[a[i]]++;
		sum+=a[i];
	}
	ll q;
	cin>>q;
	for(ll i=0;i<q;i++)
	{
		ll b,c;
		cin>>b>>c;
		sum+=(c-b)*arr[b];
		printf("%lld\n",sum);
		arr[c]+=arr[b];
		arr[b]=0;
	}
}



Measured memory_bytes: 5252
#include <stdio.h>
int main(void){
    long int a,b,x,count=0;
    scanf("%ld%ld%ld", &a,&b,&x);
    if(a==0) count = b/x+1;
    else count = b/x-(a-1)/x;
    printf("%ld", count);
    return 0;
}

Measured memory_bytes: 1716
//https://atcoder.jp/contests/abc160/tasks/abc160_d
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
const ll LINF = 0x1fffffffffffffff;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
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;}

template< typename T >
struct edge {
	int src, to;
	T cost;
	edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
	edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}
	edge &operator=(const int &x) {
		to = x;
		return *this;
	}
	operator int() const { return to; }
};

template< typename T>
struct node {
	vector<edge<T>> edges;
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< node< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

//s start node
//return 各nodeへの最短の距離が入る,numeric_limits<T>::max()の場合、到達できない
template< typename T >
vector< T > dijkstra(const WeightedGraph< T > &g, int s, vector<int>& prev) {
	const auto INF = numeric_limits<T>::max();
	vector<T> dist(g.size(), INF);
	prev.assign(g.size(),-1);

	using Pi = pair<T, int>; //dist,node id
	priority_queue<Pi, vector<Pi>, greater<Pi>> que;
	dist[s] = 0;
	que.emplace(dist[s], s);
	while(!que.empty()) {
		T cost;
		int idx; //node id
		tie(cost, idx) = que.top();
		que.pop();
		if(dist[idx] < cost)
			continue;
		for(auto &e : g[idx].edges) {
			auto next_cost = cost + e.cost;
			if(dist[e.to] <= next_cost)
				continue;
			dist[e.to] = next_cost;
			prev[e.to] = idx;
			que.emplace(dist[e.to], e.to);
		}
	}
	return dist;
}
vector<int> get_path(int t, const vector<int>& prev){ //頂点tへの最短路
	vector<int> path;
	for(; t != -1;t=prev[t]){
		path.push_back(t);
	}
	reverse(path.begin(), path.end());
	return path;
}

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

  WeightedGraph<ll> graph(N+1);
  FOR(i,1,N){
    graph.at(i).edges.emplace_back(i+1,1);
    graph.at(i+1).edges.emplace_back(i,1);
  }
  graph.at(X).edges.emplace_back(Y,1);
  graph.at(Y).edges.emplace_back(X,1);

  vector<ll> ans(N);
  FOR(i,1,N+1){    
	vector<int> prev;
    auto result = dijkstra(graph,i,prev);
    FOR(j,i+1,N+1){
      auto d = result.at(j);
      ans.at(d)++;
    }
  }
  FOR(i,1,ans.size()){
    cout<<ans.at(i)<<endl;
  }

  return 0;
}

Measured memory_bytes: 384
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

que = deque()
for i in range(N):
    if i % 2 == 0:
        que.append(A[i])
    else:
        que.appendleft(A[i])
if N % 2:
    que.reverse()
print(*que)


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

void swap(double *a, double *b)
{
  double tmp = *a;
  *a = *b;
  *b = tmp;
}

double angle(double x, double y)
{
  double angle = acos(x/sqrt(x*x+y*y));
  if(y<0){
    angle = 2*M_PI-angle;
  }

  return angle;
}

int main(void)
{
  double x1,y1,x2,y2,x3,y3,xp,yp;
  while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &xp, &yp) != EOF){
    double alpha = angle(x1-xp, y1-yp);
    double beta = angle(x2-xp, y2-yp);
    double gamma = angle(x3-xp, y3-yp);
    
    if(alpha>beta){
      swap(&alpha, &beta);
    }
    if(beta>gamma){
      swap(&beta, &gamma);
    }
    if(alpha>beta){
      swap(&alpha, &beta);
    }

    if(beta-alpha<M_PI && gamma-beta<M_PI && gamma-alpha>M_PI){
      printf("YES\n");
    }else{
      printf("NO\n");
    }
  }

  return 0;
}

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


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

	map<ll, int> mp;
	for(int i=0;i<N;i++) {
		ll a;
		cin >> a;
		mp[-a]++;
	}

	int ans = 0;
	while(!mp.empty()) {
		auto it = mp.begin();
		ll a = -it->first;
		ll p = 1;
		while(p <= a) {
			p <<= 1;
		}
		ll target = -(p - a);

		it->second--;
		if(it->second == 0) {
			mp.erase(it);
		}

		auto nit = mp.find(target);
		if(nit != mp.end()) {
			ans++;
			nit->second--;
			if(nit->second == 0) {
				mp.erase(nit);
			}
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 12800
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int n;

void solve(){
    cin >> n;
    if(n%2==1) cout << n/2+1 << endl;
    else cout << n/2 << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}

Measured memory_bytes: 256
n = int(input())
a = []
for i in range(n): a.append(int(input()))

mini = a[0]
max_sub = -float("inf")
for i in range(1, n):
    if a[i] - mini > max_sub:
        max_sub = a[i] - mini
    
    if a[i] < mini: mini = a[i]

print(max_sub)


Measured memory_bytes: 13616
### constant

NS = 5

DXYS = [[1, 0], [0, -1], [-1, 0], [0, 1]]

XM = 0
XP = 1
YM = 2
YP = 3
ZM = 4
ZP = 5

### subroutines

def check_dice(sts)
  sx = sy = 0
  while sts[sy][sx] == 0
    sx += 1
    if sx >= NS
      sx = 0
      sy += 1
      return false if sy >= NS
    end
  end
  #p [sx, sy]

  folded = NS.times.map{NS.times.map{false}}
  folded[sy][sx] = true
  sides = []
  sides[ZM] = sts[sy][sx]
  q = [[sx, sy, ZM, [XP, YM, XM, YP]]]

  while ! q.empty?
    x, y, sd, edges = q.shift

    for d in (0..3)
      x0 = x + DXYS[d][0]
      y0 = y + DXYS[d][1]
      if x0 >= 0 && x0 < NS && y0 >= 0 && y0 < NS &&
          sts[y0][x0] != 0 && ! folded[y0][x0]
        folded[y0][x0] = true

        d2 = (d + 2) % 4
        sd2 = (sd ^ 1)

        sd0 = edges[d]
        edges0 = edges.clone
        edges0[d] = sd2
        edges0[d2] = sd

        return false if ! sides[sd0].nil?
        sides[sd0] = sts[y0][x0]

        sd1 = (sd0 ^ 1)
        return false if ! sides[sd1].nil? && sides[sd0] + sides[sd1] != 7

        q << [x0, y0, sd0, edges0]
      end
    end
  end

  for i in (0..5)
    return false if sides[i].nil?
  end

  true
end

### main

n = gets.to_i

n.times do
  sts = []

  sn = 0
  dcnts = [0] * 7
  invalid = false

  NS.times do
    ds = gets.split.map(&:to_i)
    sts << ds

    for d in ds
      next if d == 0
      sn += 1
      invalid = true if dcnts[d] > 0
      dcnts[d] += 1
    end
  end
  #p sts
  #p [invalid, dcnts]

  if invalid || sn != 6
    puts 'false'
    next
  end

  puts (check_dice(sts) ? 'true' : 'false')
end

Measured memory_bytes: 6188
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MIN(a, b)  (((a) < (b)) ? (a) : (b)) 
#define MAX(a, b)  (((a) > (b)) ? (a) : (b)) 
int main(void) {
    long long   n,a,b;
    scanf("%lld" "%lld" "%lld",&n,&a,&b);
    long long t =b-a;
    
    if(t%2==0){
        printf("%lld",t/2);
        return 0;
    }else{
        long long ans ;
        ans = MIN(a-1,n-b)+(t+1)/2;
        printf("%lld",ans);
        return 0;       
        }
    }

Measured memory_bytes: 128
function main(input) {
    // 入力値の分離
    param = input.split(" ");
    var hour = param[2] - param[0];
    var min = param[3] - param[1];
    if(min < 0 ){
      hour -= 1;
      min = min * (-1);
      min = 60 - min;
    }
    const limit = (hour * 60) + min
    var result = limit - param[4];
    console.log(result);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 29636
#include<stdio.h>

int main(){
	int i,k,n=0,m[31]={},j,a,s,rac=0;

	scanf("%d%d",&n,&s);
	
	for(i=0;i<n;i++){
		scanf("%d",&a);
				for(j=0;j<a;j++){
					scanf("%d",&k);
					m[k]++;	
				 }
	}

	for(i=1;i<s+1;i++){
	if(m[i] == n)
		rac++;
	}

	printf("%d\n",rac);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	ll a,b,n,x;
	cin >> a >> b >> n;
	if(n>=b) x=b-1;
	else if(n<b) x=n;
	cout << floor((a*x)/b)-a*floor(x/b) << endl;
	return 0;
} 

Measured memory_bytes: 3804
#include <vector>
#include <stdio.h>
#include <iostream>
using namespace std;

const string YES = "Yes";
const string NO = "No";

void solve(std::vector<std::vector<long long> > A, long long N, std::vector<long long> b){
    vector< vector<long long> > Check = A;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            for(int n = 0; n < N; n++) {
                if(A[i][j] == b[n]) {
                    A[i][j] = -1;
                }
            }
        }
    }

    // Checkで３つ連続に並んでいるものがあるか調べる

    // 盾サーチ
    for(int i = 0; i < 3; i++) {
        if(A[0][i] == -1 && A[1][i] == -1 && A[2][i] == -1) {
            cout << YES << endl;
            return;
        }
    }

    // 横列サーチ
    for(int i = 0; i < 3; i++) {
        if(A[i][0] == -1 && A[i][1] == -1 && A[i][2] == -1) {
            cout << YES << endl;
            return;
        }
    }

    // ななめ
    if(A[0][0] == -1 && A[1][1] == -1 && A[2][2] == -1) {
        cout << YES << endl;
        return;
    }

    if(A[0][2] == A[1][1] && A[1][1] == A[2][0]) {
        cout << YES << endl;
        return;
    }

    cout << NO << endl;

}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::vector<std::vector<long long> > A(3, std::vector<long long>(3));
    for(int i = 0 ; i < 3 ; i++){
        for(int j = 0 ; j < 3 ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    long long N;
    scanf("%lld",&N);
    std::vector<long long> b(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&b[i]);
    }
    solve(std::move(A), N, std::move(b));
    return 0;
}


Measured memory_bytes: 256
// Ver19.03
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF (1 << 29) * 2
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  int a;
  scanf("%d", &a);
  printf("%d\n", a * 800 - a / 15 * 200);
  return 0;
}


Measured memory_bytes: 128
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    def main():
        N,M,K=map(int,input().split())
        for k in range(N+1):
            for l in range(M+1):
                if K==k*M+l*N-k*l*2:
                    return 'Yes'
        return 'No'

    print(main())



resolve()

Measured memory_bytes: 38768
#include<iostream>
using namespace std;
int main(){
	long long n, blue, red, hasil = 0;
	cin>>n>>blue>>red;
	if(blue==0&&red==0){
		cout<<0;
		return 0;
	}
	hasil+=n/(blue+red); // hasil = 20 / 7 = 2
	n-=hasil*(blue+red); // n = 20 - 14 = 6
	hasil*=blue; // hasil = 2 * 3 = 6
	if(n > blue)hasil+=blue; // 6 == 6 => hasil = 6 + 6 = 12
	else hasil+=n;
	cout<<hasil;
}

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

fn dfs(v: usize, c: usize, iro: &mut Vec<usize>, g: &Vec<Vec<usize>>) -> bool {
    iro[v] = c;
    let mut res = true;
    for nv in 0..g.len() {
        if nv != v && g[v][nv] == 1 {
            if iro[nv] == c {
                return false;
            }
            if iro[nv] == 2 {
                res &= dfs(nv, c ^ 1, iro, g);
            }
        }
    }
    res
}

fn main() {
    let mut s: String = String::new();
    stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let mut g: Vec<Vec<usize>> = vec![vec![0; n]; n];
    for i in 0..n {
        let s: Vec<char> = itr.next().unwrap().chars().collect();
        for j in 0..s.len() {
            if s[j] == '0' {
                g[i][j] = 1 << 30;
            } else {
                g[i][j] = 1;
            }
        }
        g[i][i] = 0;
    }
    let mut iro = vec![2; n];
    // cycle check
    if dfs(0, 0, &mut iro, &g) {
        for k in 0..n {
            for i in 0..n {
                for j in 0..n {
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
                }
            }
        }
        let mut ans = 0;

        for i in 0..n {
            for j in 0..n {
                ans = max(ans, g[i][j]);
            }
        }
        println!("{}", ans + 1);
    } else {
        println!("-1");
    }
}


Measured memory_bytes: 4352
#include<stdio.h>
#include<string.h>
#define MAX 1046527
#define LEN 12

char A[MAX][LEN];

int getChar(char ch)
{
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
  else return 0;
}

long long getkey(char str[])
{
  long long cnt = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ )
    {
      cnt += p*(getChar(str[i]));
      p *= 5;
    }
  return cnt;
}

int a1(int key)
{
  return key%MAX;
}

int a2(int key)
{
  return 1+(key%(MAX-1));
}

int findkey(char str[])
{
  long long i,key,a;
  key = getkey(str);
  i=0;
  while(1)
    {
      a=(a1(key)+i*a2(key))%MAX;
      if(strcmp(A[a],str)==0)return 1;
      else if(strlen(A[a])==0)return 0;
      i++;
    }
  return 0;
}

int insertkey(char str[])
{
  long long i,key,a;
  key=getkey(str);
  i=0;
  while(1)
    {
       a=(a1(key)+i*a2(key))%MAX;
       if(strcmp(A[a],str)==0)return 1;
       else if(strlen(A[a])==0)
	 {
	   strcpy(A[a],str);
	   return 0;
	 }
       i++;
    }
  return 0;
}

int main(){
    int i, n, a;
    char str[LEN], order[9];
    for ( i = 0; i < MAX; i++ ) A[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", order, str);
	
	if ( order[0] == 'i' ){
	    insertkey(str);
	} else {
	    if (findkey(str)==1){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}

Measured memory_bytes: 12872
temp_S = [1,2,3,4,5,6,7,8,9,10,11,12,13]
temp_H = [1,2,3,4,5,6,7,8,9,10,11,12,13]
temp_C = [1,2,3,4,5,6,7,8,9,10,11,12,13]
temp_D = [1,2,3,4,5,6,7,8,9,10,11,12,13]

n = gets.chomp.to_i #amount of temochi card
n.times do
	str = gets.chomp.split(" ")
	case str[0]
	when "S"
		temp_S.delete(str[1].to_i)
	when "H"
		temp_H.delete(str[1].to_i)
	when "C"
		temp_C.delete(str[1].to_i)
	when "D"
		temp_D.delete(str[1].to_i)
	else
	end
end

for n in 0...temp_S.size do
	if temp_S[n] != nil
		puts "S " + temp_S[n].to_s
	end
end
for n in 0...temp_H.size do
	if temp_H[n] != nil
		puts "H " + temp_H[n].to_s
	end
end
for n in 0...temp_C.size do
	if temp_C[n] != nil
		puts "C " + temp_C[n].to_s
	end
end
for n in 0...temp_D.size do
	if temp_D[n] != nil
		puts "D " + temp_D[n].to_s
	end
end

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

namespace AtCoder.Abc
{
    //https://atcoder.jp/contests/abc141/tasks/abc141_a
    public class QuestionA
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            string[] inputStrArray = Console.ReadLine().Split(' ');
            for(int i=0; i<=4; i++)
            {
                if(inputStrArray[i]=="0")
                {
                    Console.WriteLine((i + 1).ToString());
                    break;
                }
            }
            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 25968
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
// using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<ll> A(N);
  for (auto &it : A)
    cin >> it;
  ll res = 0;
  int right = 0;
  int sum = 0; // AND 和
  for (int left = 0; left < N; left++)
  {
    while (right < N && (sum ^ A[right]) == (sum + A[right]))
    {
      sum += A[right];
      right++;
    }
    res += right - left;
    if (left == right)
      right++;
    else
    {
      sum -= A[left]; // A[left]を削除　(sum^=A[left]でも可)
    }
  }
  cout << res << endl;
  return 0;
}

// 基本的にxor和<=加算和が成り立つ．例えばx=10101,y=1001O(二進法)としたときxxory = 11100(1の位が消える), x + y = 11110(1の位が繰り上がる)という感じになる．x+yは繰り上がりが残るのに対してxxoryは1が被ると消えてしまう．そう考えるとxxory = x + y <=> 二進法におけるどの桁を見てもxとyのうちビットが立っているのは高々1個のみ．すなわち条件を満たす区間の部分区間も条件を満たす．-> 尺取り法を用いる


Measured memory_bytes: 1792
t = int(raw_input())

for i in xrange(t):
    n, k = [int(_) for _ in raw_input().split()]

    x = [int(_) for _ in raw_input().split()]
    d = [x[j + 1] - x[j] for j in xrange(n - 1)]
    d.sort(reverse=True)
    print(x[-1] - x[0] - sum(d[:k - 1]))

Measured memory_bytes: 19532
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;


vector<int> x[2550];
vector<int> y[2550];

map<int,int> memo[2550];

int sx,sy,gx,gy;
int n;
int f(int pos , int w){
	if(memo[pos].count(w)) return memo[pos][w];
	if(pos==n-1){
		return 0;
	}
	int ans = 99999999;
	for(int i = 0 ; i < x[pos+1].size() ; i++){
		ans = min(ans,f(pos+1,i)+abs(x[pos+1][i]-x[pos][w])+abs(y[pos+1][i]-y[pos][w]));
	}
	return memo[pos][w] = ans;
}
int main(){
	int W,H;
	while(cin >> W >> H && W){
		for(int i = 0 ; i < 2550 ; i++)
			x[i].clear() , y[i].clear() , memo[i].clear();
		int m = 0;
		for(int i = 0 ; i < H ; i++){
			for(int j = 0 ; j < W ; j++){
				string p;cin>>p;
				if(p=="S"){
					sx = j , sy = i;
				}else if(p=="G"){
					gx = j , gy = i;
				}else if(p != "."){
					stringstream ss(p);
					int o; ss >> o;
					x[o].push_back(j);
					y[o].push_back(i);
					m = max(o,m);
				}
			}
		}

		x[0].push_back(sx);
		y[0].push_back(sy);
		x[m+1].push_back(gx);
		y[m+1].push_back(gy);
		n = m+2;
		cout << f(0,0) << endl;
	}
}

Measured memory_bytes: 1504
# -*- coding: UTF-8 -*-
#Selection Sort

#標準入力から
N = int(input()) #要素数
A = list(map(int,input().split())) #ソート対象（スペース区切り→配列に展開）
#交換回数
cnt = 0 

#Sort処理
for i in range(N):
    cnt_flg = 0
    minj = i
    for j in range(i,N):
        if A[j] < A[minj]:
            minj = j
            cnt_flg = 1
    tmp = A[i]
    A[i] = A[minj]
    A[minj] = tmp
    if cnt_flg == 1: cnt+=1

#回答
print(' '.join(map(str,A)))
print(cnt)



Measured memory_bytes: 5600
A, B, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
ans = min(a[1:]) + min(b[1:])
for _ in range(m):
    x, y, c = map(int, input().split())
    ans = min(ans, a[x] + b[y] - c)
print(ans)

Measured memory_bytes: 18556
n = int(input())
a = [i for i in input().split()]
b = [a[i] for i in range(n)]
def bubbleSort(A):
    for i in range(n):
        for j in range(i+1,n)[::-1]:
            if int(A[j][1]) < int(A[j-1][1]):
                A[j], A[j-1] = A[j-1], A[j]
    return A

def selectionSort(A):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if int(A[j][1]) < int(A[minj][1]):
                minj = j
        A[i], A[minj] = A[minj], A[i]
    return A

bubbleSort(a)
selectionSort(b)

print(' '.join(a))
print("Stable")
print(' '.join(b))
if a == b:
    print("Stable")
else:
    print("Not stable")



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


void solve(long long A, long long B){
    vector<long long> vec = {A+B, A-B, A*B};
    cout << *max_element(vec.begin(), vec.end()) << endl;
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256
import sys
from collections import deque
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
G = dict([(i,[]) for i in range(1,N+1)])
for i in range(1,N+1):
  G[i].append(A[i])

l = deque([A[1]])
seen = [False for i in range(N+1)]
seen[1] = True
d = [0 for i in range(N+1)]
d[A[1]] = 1
if A[1] == 1:
  print(1)
  sys.exit()

for i in range(K):
  v = l.popleft()
  if seen[v] == False:
    seen[v] = True
    l.append(A[v])
    if seen[A[v]] == True: 
      a = d[A[v]]
      b = d[v] + 1 - a
    else:  
      d[A[v]] = d[v] + 1
  else:  
    start = v
    break  
  if i == K-1:
    print(v)
    sys.exit()

kaisu = (K-a)%b
p = start
for i in range(kaisu):
  p = A[p]
print(p)  

Measured memory_bytes: 74560
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <cstdlib>

using namespace std;

int main()
{
    string s;   cin >> s;
    int ans = 999;
    string t;
    for (int i = 0; i < s.size() - 2; i++){
        t = s.substr(i, 3);
        int a = fabs(753 - stoi(t));
        ans = min(ans, a);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define de(x) cout << #x << "=" << x << ", "
#define dd cout << '\n';
#define XinAi ios::sync_with_stdio(0), cin.tie(0);
#define F first
#define S second
#define int long long
using namespace std;
typedef pair<int,int> pii;

int a, c;
string b;

signed main()
{
    cin >> a >> b;
    int res = 0;
    c += b[0]-'0', c*=10;
    c += b[2]-'0', c*=10;
    c += b[3]-'0';
    res = a * c / 100;
    cout << res << '\n';
}

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

int main(){
  string S;
  cin >> S;
  int ans = 0;
  if(S.at(0) == '1')ans++;
  if(S.at(1) == '1')ans++;
  if(S.at(2) == '1')ans++;
  cout << ans << endl;
}
  


Measured memory_bytes: 256
import java.util.Scanner

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val a = sc.nextInt()
    val b = sc.nextInt()
    val result = press(0, a, b)
    println(result)
}

private fun press(coin: Int, buttonSizeA: Int, buttonSizeB: Int, pressCount: Int = 0): Int {
    if (pressCount >= 2) {
        return coin
    }
    return when (buttonSizeA > buttonSizeB) {
        true -> press(coin + buttonSizeA, buttonSizeA - 1, buttonSizeB, pressCount + 1)
        false -> press(coin + buttonSizeB, buttonSizeA, buttonSizeB - 1, pressCount + 1)
    }
}


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

ll dp[3005][3005];

int main() {
  ll N, T;
  cin >> N >> T;
  vector<pair<int,int> > AB(N);
  REP(i,N) {
    int a,b;
    cin >> a >> b;
    AB[i] = make_pair(a,b);
  }
  sort( AB.begin(), AB.end() ) ;
//  REP(i,N) cout << AB[i].first << " " << AB[i].second << endl;
  REP(i,N) {
    REP( ti, T ) {
      if ( ti >= AB[i].first) dp[i+1][ti] = max(dp[i][ti-AB[i].first] + AB[i].second, dp[i][ti] );
      else dp[i+1][ti] = dp[i][ti];
    }
  }
  ll ans = 0;
  REPI(i,0,N-1) {
    REPI(j,i+1,N) {
      ans = max( ans, dp[i+1][T-1] + AB[j].second );
    }
  }
//  REP(i,T) {
//    REP(j,N+1) {
//      printf("%3d ",dp[j][i]);
//    }
//    cout << endl;
//  }

  cout << ans << endl;
}


Measured memory_bytes: 70656
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n = readline() |> parseInt
	a,b = readline() |> split |> parseMap
	p = readline() |> split |> parseMap
	ca = 0
	cb = 0
	for i in 1:n
		if p[i] <= a
			ca += 1
		elseif p[i] <= b
			cb += 1
		end
	end
	println(min(ca,cb,n-ca-cb))
end

main()


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

const int INF = 1e18;
int n,cnt;
int a[200010];
int L[100010],R[100010];

void merge(int l,int m,int r){
  int n1 = m-l;
  int n2 = r-m;
  for(int i = 0; i < n1; i++) L[i] = a[l+i];
  for(int i = 0; i < n2; i++) R[i] = a[m+i];
  L[n1] = R[n2] = INF;
  int i = 0,j = 0;
  for(int k = l; k < r; k++){
    if(L[i] <= R[j]) a[k] = L[i++];
    else {
      a[k] = R[j++];
      cnt += n1-i; //mid + j - k -1;
    }
  }
}

void mergesort(int l,int r){
  if(l+1 < r){
    int m = (l+r)/2;
    mergesort(l,m);
    mergesort(m,r);
    merge(l,m,r);
  }
}

signed main(){

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

  mergesort(0,n);

  cout << cnt << endl;

  return 0;
}



Measured memory_bytes: 6220
h,w = map(int, input().split())
s = []
for i in range(h):
	a = input()
	s.append(a)
ans = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(h):
	for j in range(w):
		visited = [[0 for p in range(w)] for q in range(h)]
		c = 0
		if s[i][j] == "#":
			continue
		else:
			v = [[i,j]]
			visited[i][j] = 1
			while v:
				x, y = v.pop(0)
				for k in range(4):
					d = x + dx[k]
					e = y + dy[k]
					if d < 0 or e < 0 or d >= h or e >= w or visited[d][e] != 0 or s[d][e] == "#":
						continue
					visited[d][e] = visited[x][y] + 1
					v.append([d,e])
			for ii in range(h):
				for jj in range(w):
					ans = max(ans,visited[ii][jj])
print (ans-1)


Measured memory_bytes: 3188
n = int(input())
s = [input() for _ in range(n)]

for i in range(n):
    s[i] = ''.join(sorted(s[i]))
# print(s)
t = {}
for i in range(n):
    if s[i] in t:
        t[s[i]] += 1
    else:
        t[s[i]] = 1
# print(t)
print(sum(t[k]*(t[k]-1)//2 for k in t))


Measured memory_bytes: 19476