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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int x;
	int y;
	cin>>x>>y;
	for (int i = 0; i <= x; ++i){
		int t = 4*i + (x-i)*2;
		if (t == y){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
const int maxn=5e5+5;
const int MOD=1e9+7;


int a[maxn],c[maxn];
int mp[maxn];
int n;
struct qq{
    int l,r;
    int index;
}q[maxn];
int cmp(qq x,qq y){
    return x.r<y.r;
}
int lowbit(int x){
    return x&(-x);
}
void update (int i,int k){
    int x=i;
    while(i<=n){
        c[i]+=k;
        i+=lowbit(i);
    }
}
ll getsum(int i){
    ll ans=0;
    int x=i;
    while(i>0){
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
int ans[maxn];
int main()
{
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>q[i].l>>q[i].r;
        q[i].index=i;
    }
    sort(q+1,q+1+m,cmp);
    int next=1;
    for(int i=1;i<=m;i++){
        for(int j=next;j<=q[i].r;j++){
            if(mp[a[j]]){
                update(mp[a[j]],-1);
            }
            update(j,1);
            mp[a[j]]=j;
        }
        next=q[i].r+1;
        ans[q[i].index]=getsum(q[i].r)-getsum(q[i].l-1);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
}




Measured memory_bytes: 17360
#include<bits/stdc++.h>
using namespace std;
long long a[1000000];
int main()
{
 	ios_base::sync_with_stdio(false);
	cin.tie(0);
 	int n;
 	cin>>n;
 	for(int i=0;i<n;i++)
 	{
 		cin>>a[i];
	}
	sort(a,a+n);
	for(int i=0;i<n;i++)
	{
		if(a[i]==a[i+1])
		{
			cout<<"NO";
			return 0;
		}
	}
	cout<<"YES";
	return 0;
}

Measured memory_bytes: 1792
N, Y = map(int, input().split())

def func():
    for x in range(Y//10000+1):
        for y in range(Y//5000+1):
            if N-x-y>=0:
                if 1000*N+9000*x+4000*y==Y:
                    print(x, y, N-x-y)
                    return None
    print(-1, -1, -1)
    return None

func()


Measured memory_bytes: 3060
# coding: utf-8
# Your code here!
S = input()
flag1 = False
flag2 = False

num1 = int(S[0] + S[1])
num2 = int(S[2] + S[3])

if num1 >= 0 and (num2 >= 1 and num2 <= 12):
    flag1 = True

if (num1 >= 1 and num1 <= 12) and num2 >= 0:
    flag2 = True
    


if flag1 == True and flag2 == False:
    print("YYMM")
elif flag1 == False and flag2 == True:
    print("MMYY")
elif flag1 == True and flag2 == True:
    print("AMBIGUOUS")
else:
    print("NA")


Measured memory_bytes: 38256
#include "atcoder/all"
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

using namespace std;
using namespace atcoder;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VV(T, a, b, c) vector<vector<T>>(a, vector<T>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define VVV(T, a, b, c, d)                                                     \
  vector<vector<vector<T>>>(a, vector<vector<T>>(b, vector<T>(c, d)))
#define SP(a) fixed << setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll T;
  cin >> T;
  REP(i, T) {
    ll n, m, a, b;
    cin >> n >> m >> a >> b;
    cout << floor_sum(n, m, a, b) << endl;
  }

  return 0;
}


Measured memory_bytes: 3640
import math
import itertools

N = int(input())
x, y = [], []
for _ in range(N):
  a, b = map(int, input().split())
  x.append(a)
  y.append(b)
  
ans = 0
for r in itertools.permutations([i for i in range(N)]):
  for i in range(1, N):
    ans += math.sqrt((x[r[i]]-x[r[i-1]])**2 + (y[r[i]]-y[r[i-1]])**2)
ans /= math.factorial(N)
print(ans)

Measured memory_bytes: 9052
#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define FORR(i,a,b) for (int i = b - 1; i >= a; --i)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) FORR(i,0,n)

ll myabs(ll a) {
	if (a < 0) return -a;
	else return a;
}

int main() {
	ll X, K, D;
	cin >> X >> K >> D;

	if (X >= 0) {
		ll n = X / D + 1;
		if (K < n) {
			cout << myabs(X - D * K) << endl;
		}
		else {
			if (n % 2 == 0) {
				if (K % 2 == 0) cout << myabs(X - D * n) << endl;
				else cout << myabs(X - D * (n - 1)) << endl;
			}
			else {
				if (K % 2 == 0) cout << myabs(X - D * (n - 1)) << endl;
				else cout << myabs(X - D * n) << endl;
			}
		}
	}
	else {
		ll n = -X / D + 1;
		if (K < n) {
			cout << myabs(X + D * K) << endl;
		}
		else {
			if (n % 2 == 0) {
				if (K % 2 == 0) cout << myabs(X + D * n) << endl;
				else cout << myabs(X + D * (n - 1)) << endl;
			}
			else {
				if (K % 2 == 0) cout << myabs(X + D * (n - 1)) << endl;
				else cout << myabs(X + D * n) << endl;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 3632
n,m = list(map(int,input().strip().split()))

path = [[] for i in range(n)]

for i in range(m):
  a,b = list(map(int,input().split()))
  path[a-1].append(b-1)
  path[b-1].append(a-1)

for j in path[0]:
  if n-1 in path[j]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Measured memory_bytes: 50136
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <set>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define ri rd<int>
using namespace std;
const int maxN = 4e5 + 7;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

inline void NIE() {puts("NO"); exit(0);}
inline void TAK() {puts("YES"); exit(0);}

int R, C, ALL, n, m, tt;

set<int> S;

struct pt {
	int x, y;
	inline void input() {x = ri(), y = ri();}
	inline bool operator < (const pt &v) const {return x < v.x;}
}a[maxN];

inline int id(const pt &v) {
	if (v.y == 0 && v.x < R) return v.x;
	if (v.x == R && v.y < C) return R + v.y;
	if (v.y == C && v.x > 0) return R + C + (R - v.x);
	if (v.x == 0 && v.y > 0) return R + C + R + (C - v.y);
	return -1;
}

int main() {

	R = ri(), C = ri(), ALL = 2 * R + 2 * C; n = ri();
	rep (i, 1, n) {
		pt p, q; p.input(), q.input();
		int x = id(p), y = id(q);
		if (x == -1 || y == -1) continue;
		if (x > y) swap(x, y);
		a[++m] = (pt){x, y}; a[++m] = (pt){y, -1};
		a[++m] = (pt){x + ALL, y + ALL}; a[++m] = (pt){y + ALL, -1};
	}
	sort(a+1, a+m+1);
	rep (i, 1, m) {
		if (a[i].y == -1) S.erase(a[i].x);
		else {
			set<int>::iterator it = S.lower_bound(a[i].x);
			if (it == S.end() || *it > a[i].y) S.insert(a[i].y);
			else NIE();
		}
	}

	TAK();
	return 0;
}

Measured memory_bytes: 5760
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<tuple>
#include<set>
#include<map>
#include<cctype>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
#define tget(a,b) get<a>(b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e16;
const int MOD = 1e9 + 7;


int N,p[15];


int main(void) {
	cin >> N;
	int ma = 0,ans=0;
	FOR(i, 0, N) {
		cin >> p[i]; ma = max(ma, p[i]);
		ans += p[i];
	}
	ans -= ma / 2;
	ct(ans);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int n,a,k[100000]={},e,i;
  long ans=1;
  scanf("%d",&n);
  for (i=0;i<n;i++){
    scanf("%d",&a);
    k[a]++;
  }
  k[0]++;
  for (i=1-n%2;i<n;i+=2){
    if (k[i]!=2){
      printf("0\n");
      return 0;
    }
  }
  e=(n-n%2)/2;
  for (i=0;i<e;i++) ans=ans*2%1000000007;
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector> //可変長配列
#include <queue> //キュー
#include <unordered_map> //ハッシュ連想配列
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ll long long int
#define INFTY (1<<21)

using namespace std;

int N,A[2][100];

int rec(int i, int j){
    if(j==N) return 0;
    else if(i==1)
        return A[i][j] + rec(i,j+1);
    else
        return A[i][j] + max(rec(i,j+1),rec(i+1,j));
}

int main(void){
    cin.sync_with_stdio(false);
    cin>>N;
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < N; j++){
            cin>>A[i][j];
        }
    }
    cout<<rec(0,0)<<endl;
    return 0;
}

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

const double EPS = 1e-5;
const double pi = 3.141592653589793;

double ix1, ix2, ix3, ixp;
double iy1, iy2, iy3, iyp;

//2点の座標から辺の長さを求める
double sideLength(double x1, double y1, double x2, double y2) {
    return sqrt( pow(fabs(x1-x2), 2.0) + pow(fabs(y1-y2), 2.0) );
}

//3辺の長さから三角形の面積を求める
double heron(double a, double b, double c) {
    double s = (a + b + c) / 2;
    return sqrt( s * (s-a) * (s-b) * (s-c) );
}

//余弦定理より角度を求める
double getAngle(double a, double b, double c) {
    double val = (b*b + c*c - a*a) / (2 * b * c);
    return acos(val);
}

int solve1() {
    double ab = sideLength(ix1, iy1, ix2, iy2),
           bc = sideLength(ix2, iy2, ix3, iy3),
           ca = sideLength(ix3, iy3, ix1, iy1),
           ap = sideLength(ix1, iy1, ixp, iyp),
           bp = sideLength(ix2, iy2, ixp, iyp),
           cp = sideLength(ix3, iy3, ixp, iyp);
    
    double Sabc  = heron(ab, bc, ca);
    double Sabcp = heron(ab, bp, ap) + heron(ca, ap, cp) + heron(bc, bp, cp);
    return fabs(Sabcp - Sabc) < EPS;
}

int solve2() {
    double ab = sideLength(ix1, iy1, ix2, iy2),
           bc = sideLength(ix2, iy2, ix3, iy3),
           ca = sideLength(ix3, iy3, ix1, iy1),
           ap = sideLength(ix1, iy1, ixp, iyp),
           bp = sideLength(ix2, iy2, ixp, iyp),
           cp = sideLength(ix3, iy3, ixp, iyp);
    
    double apb = getAngle(ab, ap, bp),
           apc = getAngle(ca, ap, cp),
           bpc = getAngle(bc, bp, cp);
           
    double sum = apb + apc + bpc;
    return (2*pi - sum) < EPS;
}

int main() {
     while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &ix1, &iy1, &ix2, &iy2, &ix3, &iy3, &ixp, &iyp) != EOF){
         if(solve2()) {
         	printf("YES\n");
         } else {
         	printf("NO\n");
         }
     }
}


Measured memory_bytes: 2044
def trianglecheck(a, b, c):
    if (a + b) > c:
        return True
    return False

a = int(input())
arr = sorted(list(map(int, input().split())))
res = 0
for x in range(a - 2):
    for y in range(x + 1, a - 1):
        for z in range(y + 1, a):
            if arr[x] != arr[y] and arr[y] != arr[z] and arr[z] != arr[x] and trianglecheck(arr[x], arr[y], arr[z]):
                res += 1      
print(res)

Measured memory_bytes: 9108
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define length(X) (int)X.size()
using namespace std;
typedef pair <int, int> ii;

const ll siz = 1e3 + 10;
const ll SIZ = 1e6 + 10;
const ll mod = 1e9;
const ll maxx = 2e9;
const ll MAXX = 1e18;

int n, q;
map <int, int> cnt;
int ans;

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen ("IN_4.INP", "r", stdin);
//    freopen ("OUT_4.OUT", "w", stdout);
    cin >> n;
    while (n--)
    {
        int a;
        cin >> a;
        cnt[a]++;
        ans += a;
    }
    cin >> q;
    while (q--)
    {
        int b, c;
        cin >> b >> c;
        ans += (cnt[b] * (c - b));
        cout << ans << "\n";
        cnt[c] += cnt[b];
        cnt[b] = 0;
    }
    return 0;
}


Measured memory_bytes: 9532
import sys

x,n=map(int,input().split())

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

d=0
for i in range(1000):
    if x-d not in p:
        print(x-d)
        sys.exit()
    elif x+d not in p:
        print(x+d)
        sys.exit()
    d+=1

Measured memory_bytes: 9204
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

#define MAX 100000

struct TRAMP{
    char mark;
    int number,inputed_order;
};

TRAMP cards[MAX];

int n;

int Partition(int left,int right){
    int i = left-1,pivot = cards[right].number;
    for(int start = left; start < right; start++){
        if(cards[start].number <= pivot){
                i++;
                std::swap(cards[i],cards[start]);
        }
    }

    std::swap(cards[i+1],cards[right]);

    return i+1;
}

void quickSort(int left,int right){
    if(left < right){
        int q = Partition(left,right);
        quickSort(left,q-1);
        quickSort(q+1,right);
    }
}


int main(){

    bool stableFLG = true;
    scanf("%d",&n);

    for(int i = 0; i < n; i++){
        scanf("%s %d",&cards[i].mark,&cards[i].number);
        cards[i].inputed_order = i;
    }

    quickSort(0,n-1);

    for(int i = 1; i < n; i++){
        if(cards[i].number == cards[i-1].number && cards[i].inputed_order < cards[i-1].inputed_order){
        	stableFLG = false;
        	break;
        }
    }

    if(stableFLG){
        printf("Stable\n");
    }else{
        printf("Not stable\n");
    }

    for(int i = 0; i < n; i++)   printf("%c %d\n",cards[i].mark,cards[i].number);
}



Measured memory_bytes: 4360
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
int N;
int A[200000];
long long dp[3][200000+1];
int main(){
  int i, k;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  for(k=(0);k<(3);k++){
    int i;
    for(i=(0);i<(N+1);i++){
      dp[k][i] = -4611686016279904256LL;
    }
  }
  for(i=(0);i<(N);i++){
    for(k=(1);k<(3);k++){
      chmax(dp[k][i+1], dp[k-1][i]);
    }
    for(k=(0);k<(3);k++){
      if(i>0){
        chmax(dp[k][i+1], dp[k][i-1]+ A[i]);
      }
      else{
        chmax(dp[k][i+1], -4611686016279904256LL+ A[i]);
      }
    }
    if(i<3){
      chmax(dp[i][i+1], A[i]);
    }
  }
  if(N%2==0){
    wt_L(dp[1][N]);
    wt_L('\n');
  }
  else{
    wt_L(dp[2][N]);
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20200418-1

// --- original code ---
// int N, A[2d5];
// ll dp[3][2d5+1];
// {
//   rd(N,A(N));
//   rep(k,3) rep(i,N+1) dp[k][i] = -ll_inf;
//   rep(i,N){
//     rep(k,1,3) dp[k][i+1] >?= dp[k-1][i];
//     rep(k,3) dp[k][i+1] >?= if[i>0, dp[k][i-1], -ll_inf] + A[i];
//     if(i<3) dp[i][i+1] >?= A[i];
//   }
//   wt(if[N%2==0, dp[1][N], dp[2][N]]);
// }


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

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

int main(){
    int n; cin >> n;
    vector<string> s(n); rep(i, n) cin >> s[i];
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    cout << s.size() << endl;
}

Measured memory_bytes: 9592
#include <bits/stdc++.h>
#define rep2(i,m,n) for (int i = (int)(m); i < (int)(n); i++)
#define rep(i,n) rep2(i,0,n)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
using ll = long long;
template <typename T>
T sq(T x){
  return x * x;
}

signed main (){
  string s;
  cin >> s;
  int ans;
  int A_pos = 200001;
  int Z_pos = 0;
  for(int i = 0; i < SZ(s);i++){
    if(s.at(i) == 'A'){
      A_pos = min(i,A_pos);
    }
    if(s.at(i) == 'Z'){
      Z_pos = max(i,Z_pos);
    }
  }
  cout << Z_pos - A_pos + 1 << endl; 
  return 0;
}


Measured memory_bytes: 640
a,b,c,d=map(int,input().split())


def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

cd=lcm(c,d)

nac=a//c
nbc=b//c
nad=a//d
nbd=b//d
nacd=a//(cd)
nbcd=b//(cd)


nc=nbc-nac
if a%c==0: nc+=1
#print(nc)
nd=nbd-nad
if a%d==0: nd+=1
#print(nd)
ncd=nbcd-nacd
if a%(cd)==0: ncd+=1
#print(ncd)

ans=b-a+1-(nc+nd-ncd)

print(ans)


Measured memory_bytes: 3064
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll n; cin >> n;
  map<string,ll> table;
  
  rep(i,n){
    string s; cin >> s;
    table[s]++;
  }
  
  ll maxcnt = 0;
  
  for(auto p : table){
    maxcnt = max(maxcnt,p.second);
  }
  
  for(auto p : table){
    if(p.second == maxcnt) cout << p.first << endl;
  }
  
  
  
}

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

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    if(k == 0){
        ll ans = 0;
        rep(i,n){
            ans = max(ans, a[i]);
        }
        cout << ans << endl;
        return 0;
    }

    ll lb = 0, rb = 1e9 + 7;
    while(rb - lb > 1){
        ll mid = (rb + lb) / 2;
        ll cnt = 0;
        rep(i, n) {
            if (a[i] % mid == 0) cnt--;
            ll res = a[i] / mid;
            cnt += res;
        }
        if (cnt > k) {
            lb = mid;
        } else {
            rb = mid;
        }
    }
    cout << rb << endl;
}


Measured memory_bytes: 4840
#pragma region
#pragma GCC target("avx2")
#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std; typedef long double ld; typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
#define MP make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORR(x,arr) for(auto& x:arr)
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define VPII vector<PII>
#define VPLL vector<PLL>
#define FI first 
#define SE second
#define ALL(x) (x).begin(), (x).end()
constexpr int INF=1<<30; constexpr ll LINF=1LL<<60; constexpr ll mod=1e9+7; constexpr int NIL = -1;
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
#pragma endregion
//-------------------
int F[105][11];
ll P[105][13];

int main(){
    cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15);
    int n; cin >> n;
    FOR(i,0,n-1) {
        FOR(j,0,9) {
            cin >> F[i][j];
        }
    }

    FOR(i,0,n-1) {
        FOR(j,0,10) {
            cin >> P[i][j];
        }
    }

    ll ans = -LINF;
    FOR(id,1,(1<<10)-1) {
        ll cur = 0;
        FOR(i,0,n-1) {
            ll cnt = 0;
            FOR(j,0,9) {
                if((id>>j)&1==1 and F[i][j]==1) cnt++;
            }
            cur += P[i][cnt];
        }
        chmax(ans, cur);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3552
n = int(input())

count = {'AC':0, 'WA':0,'TLE':0, 'RE':0}

for i in range(n):
    s = input() #sys.stdin.readlineは最後が改行
    count[s]+=1


print('AC x',count['AC'])
print('WA x',count['WA'])
print('TLE x',count['TLE'])
print('RE x',count['RE'])

Measured memory_bytes: 74732
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <cmath>         // sqrt
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <bits/stdc++.h> // isupper, islower, isdigit, toupper, tolower
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, n) for (int i = (a); i < (n); i++)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pl;
typedef pair<int, int> P;
typedef tuple<ll, ll, string> Tlls;

// Greatest Common Divisor (最大公約数)
ll gcd(ll a, ll b)
{
  // Eucledean algorithm
  while (a)
  {
    if (a < b)
    {
      std::swap(a, b);
    }
    a %= b;
  }
  return b;
}

// Least Common Multiple 最小公倍数
ll lcm(ll a, ll b)
{
  return a / gcd(a, b) * b;
}

// key: value of prime factor素因数分解
// value: number of prime factor
map<ll, ll> prime_factorization(ll n)
{
  map<ll, ll> prime_factors;
  for (ll i = 2; i * i <= n; i++)
  {
    while (n % i == 0)
    {
      prime_factors[i]++;
      n /= i;
    }
  }
  if (n != 1)
    prime_factors[n] = 1;
  return prime_factors;
}

// 約数リスト約数の列挙
vector<ll> get_divisors(const ll n)
{
  vector<ll> divs;
  for (ll i = 1; i < (ll)sqrt((ld)n) + 1; i++)
  {
    if (n % i == 0)
    {
      divs.push_back(i);
      if (i != n / i)
      {
        divs.push_back(n / i);
      }
    }
  }

  // 必要に応じてソート
  // sort(divs.begin(), divs.end());

  return divs;
}

int main()
{

  ll A, B;
  cin >> A >> B;
  cout << A * B << endl;

  return 0;
}


Measured memory_bytes: 3624
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) REV(SORT(V)) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b?gcd(b,a%b):a;} //最小公倍数

// デフォルト変数定義
int n,m,a,b,c,x,y,z,r;
double d,e,f;
string s,t;
//

signed main() {
  RAPID;
  IN(r);
  OUT((3 * r * r));
}

Measured memory_bytes: 256
import scala.io.StdIn.{readLine, readInt}

object Main extends App {
  val n     = readInt()
  val lines = Iterator.fill(n)(readLine())

  val offices = {
    val offices = Array.fill(4, 3, 10)(0)
    for (line <- lines) {
      val Array(b, f, r, v) = line.split(" ").map { _.toInt }
      offices(b - 1)(f - 1)(r - 1) += v
    }
    offices
  }

  val sep    = "####################"
  val result = for {
    office <- offices
    stories = office.map { _.mkString(" ", " ", "\n") }
  } yield stories.mkString

  print(result.mkString(sep + "\n"))
}



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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(a,b) for(int a=0;a<(b);++a)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
#define PI 3.14159265358979
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;
ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool compare_by_a(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}

vector<pair<int,ll>> vec[100000];
ll cost[100000];
void dfs(int now,ll COST){
    cost[now]=COST;
    int next;
    REP(i,vec[now].size()){
        next=vec[now][i].first;
        if(cost[next]<0){
            dfs(next,COST+vec[now][i].second);
        }
    }
}
int counter(int x){
    if(!x)return 0;
    return counter(x>>1)+(x&1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N=in();
    string s=in<string>();
    string t=in<string>();
    REP(i,N){
        cout<<s[i]<<t[i];
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3584
n, q = map(int, input().split())
s = input()
ranges = [list(map(int, input().split())) for _ in range(q)]

cnt = 0
cnt_list = []
# インデックスの要素 = インデックスから始まる文字が"AC"
for i in range(n):
    if i < 1:
        cnt_list.append(0)
        continue
    if s[i-1:i+1] == "AC":
        cnt += 1
    cnt_list.append(cnt)

for start, end in ranges:
    print(cnt_list[end-1] - cnt_list[start-1])


Measured memory_bytes: 30696
#include <bits/stdc++.h>
#define vi               vector<int>
#define pb(x)            push_back(x)
#define all(x)           x.begin(), x.end()
#define sortall(x)       sort(all(x))
#define sortrev(x)       sort(all(x), greater<int>())
#define debug(x)         cout << '>' << #x << ':' << x << endl;
#define int              long long
#define ld               long double
#define endl 			 "\n";
#define mp 				 make_pair
#define pii 			 <int, int>
#define lb 				 lower_bound
#define ub				 upper_bound
#define len(a)           int((a).size())
#define prec(n)          fixed<<setprecision(n)
#define cnt(n)           __builtin_popcountll(n)
#define pi               pair<int, int>
const int mod = 1000000007;
using namespace std;
const int N = 1e9; 
// int n;
// int a[N];



int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
t = 1;
// cin >>t;
while(t--){
int n;
cin >>n;
// cout << pow(N,0.2);
for(int i = -128; i<=128; i++){
	for(int j = -128 ; j<=128; j++){
		// debug(i);
		if(pow(i,5) - pow(j,5) == n){
			// cout << "d";
			cout << i << " " <<j ;
			return 0;
		}
	}
}
// cout <<"D";




}
return 0;
}

Measured memory_bytes: 4040
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>

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

#define debug(vec) for(auto v : vec) cout << v << " "; cout << endl;

#define debug2D(vec2D) for(auto vec : vec2D) { for (auto v : vec) cout << v << " "; cout << endl; } 

using namespace std;

typedef long long ll;

const long long int INF = 1 << 30; //10^10
//const ll MOD = 998244353;
const ll MOD = 1000000007;

inline void maxch(int& a, int b) { if (a < b) a = b; }

int main() {
  int n;
	cin >> n;
  
	vector<int> a(n);
	rep(i,n) cin >> a[i];

	decltype(a)::iterator Min = min_element(a.begin(), a.end()), Max = max_element(a.begin(), a.end());
	
	cout << 2*n - 1 << endl;

	if (abs(*Max) >= abs(*Min)) {
	  int maxi = Max - a.begin() + 1;
		rep(i,n) cout << maxi << " " << i+1 << endl;
		rep(i,n-1) cout << i+1 << " " << i+2 << endl;
	}
	else {
		int mini = Min - a.begin() + 1;
		rep(i,n) cout << mini << " " << i+1 << endl;
		for (int i = n; i > 1; i--) cout << i << " " << i-1 << endl;
	}
}

Measured memory_bytes: 256
while True :
    n = int(input())
    if n == 0 :
        break
    
    Team = [list(map(int, input().split())) for i in range(n)]
    Team.sort(key=lambda x: (-x[2], x[3], x[0]))
    
    Senbatsu_Syozoku = [0] * 1001
    Senbatsu_amount = 0
    for i in range(n) :
        if Senbatsu_amount < 10 and Senbatsu_Syozoku[Team[i][1]] < 3 :
            Senbatsu_amount += 1
            Senbatsu_Syozoku[Team[i][1]] += 1
            print(Team[i][0])
        elif Senbatsu_amount < 20 and Senbatsu_Syozoku[Team[i][1]] < 2 :
            Senbatsu_amount += 1
            Senbatsu_Syozoku[Team[i][1]] += 1
            print(Team[i][0])
        elif Senbatsu_amount < 26 and Senbatsu_Syozoku[Team[i][1]] == 0 :
            Senbatsu_amount += 1
            Senbatsu_Syozoku[Team[i][1]] += 1
            print(Team[i][0])


Measured memory_bytes: 5620
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>

#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
using namespace std;


signed main()
{
	int N, M, K;
	cin >> N >> M >> K;
	REP(x, N) REP(y, M)
	{
		int a = x;
		int b = N - x;
		int c = y;
		int d = M - y;
		if (a*c + b*c == K ||
			a*c + b*d == K ||
			a*d + b*c == K ||
			a*d + b*d == K)
		{
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
	return 0;
}



Measured memory_bytes: 256
fn run() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let f = 26;
    let mut dp = vec![200_000 + 1; 1 << f];
    dp[0] = 0;
    let mut bit = 0;
    for c in s.trim().chars() {
        let k = c as usize - 'a' as usize;
        bit ^= 1 << k;
        for i in 0..f {
            dp[bit] = std::cmp::min(dp[bit], dp[bit ^ (1 << i)] + 1);
        }
    }
    let ans = if bit == 0 {1} else {dp[bit]};
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 266492
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
#define ld long double
#define fi first
#define se second
#define all(uiet) uiet.begin(),uiet.end()
#define read(UIET) for(int i = 0; i < n; ++i) cin >> UIET[i]
#define out(UIET) for(int i = 0; i < n; ++i) cout << UIET[i]
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vpp vector<pair< int, int > >
#define pll pair<int , int >
#define ppll pair < pll , pll >
#define debug(n1) cout << n1 << endl
#define len(a) ((int) (a).size())
#define endl "\n"
#define mod 1000000007
const int INF=(1LL<<60)-1;
const int maxN = 1000001;

int32_t main(){
    SPEED;
    string s;
    cin >> s;
    int n = len(s);
    if(s[n - 1] == 's') cout << s + "es" ;
    else cout << s + 's';
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
 
int main() {
  vector<char> S(4);
  rep(i,4){
    cin >> S[i];
  }
  
  int count=0;
  rep(i,3){
    for(int j =i+1;j<4;j++){
      if(S[i]==S[j])count+=1;
    }
  }
  
  if(count==2)cout << "Yes" << endl;
  else cout << "No" << endl;
}



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

int Pow(int x, int y) {
	int k = 1;
	for (int i = 1; i <= y; i++)k = k * x;
	return k;
}

int main()
{

	int a,n,m;
	int ans = 0;
	int x;
	cin >> a >> n >> m;
	
	int y = 1;
		while (Pow((y+a),n)<=m) {
			x =Pow( (y+ a),n);
			if (y == x % 10 + (x / 10) % 10 + (x / 100) % 10 + (x / 1000) % 10 + (x / 10000) % 10 + (x / 100000) % 10 + (x / 1000000) % 10 + (x / 10000000) % 10) { 
				ans++;
				//cout << x << endl;////
			}
			y++;
		}
	
	cout << ans << endl;
}


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

using namespace std;

int find(string s, char c) {
	int mx = 0, cnt = 0;
	bool flag = false;
	for(int i = 0; i < s.length(); i++) {
		if(s[i] == c) {
			flag = true;
			cnt = 0;
		}
		else {
			cnt++;
			mx = max(mx, cnt);
		}
	}

	if(!flag) return INT_MAX;
	else return mx;
}

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

	string s;
	cin >> s;

	int ans = INT_MAX;

	for(char ch = 'a'; ch <= 'z'; ch++) {
		ans = min(ans, find(s, ch));
	}

	cout << ans;

	return 0;  
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
 
static class MainClass {

  public static void Main (string[] args) {
    var N = Console.ReadLine().ToCharArray().ToList();
    var K = long.Parse(Console.ReadLine());
    var ans  = '0';

     for(var i = 0; i < K; i++){
      if(N[i] != '1'){
        ans = N[i];
        Console.WriteLine(ans);
        return;
      }
    }

    Console.WriteLine('1');

  }
  
}

Measured memory_bytes: 11220
from collections import Counter

n = int(input())
s = input()

counts = Counter(s)

cnt_W, cnt_E, ans, cnt = 0, 0, counts['E'], 0
for i in range(n):
    if s[i] == 'E':
        cnt_E += 1
    
    cnt = cnt_W + (counts['E'] - cnt_E)
    ans = min(ans, cnt)
    
    if s[i] == 'W':
        cnt_W += 1

print(ans)

Measured memory_bytes: 4084
m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] + [-N] * N
for x in range(1, N + 1):
    mx = -N
    for j in range(M):
        num = x - m[A[j]]
        if num >= 0:
            if mx < dp[num] + 1:
                mx = dp[num] + 1
    if mx < 0:
        dp[x] = -N
    else:
        dp[x] = mx

A.sort(reverse=True)
nd = dp[N]
n = N
for i in range(N):
    for a in A:
        if n >= m[a] and dp[n - m[a]] == nd - 1:
            nd -= 1
            n -= m[a]
            print(a, end="")
            break
print()




Measured memory_bytes: 4304
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w;
  cin >> h >> w;
  vector<string>a(h);
  int i,j;
  for(i=0;i<h;i++)cin>>a[i];
  bool chk = true;
  while(chk){
    chk=false;
    for(i=0;i<h;i++){
      bool tmp = true;
      for(j=0;j<w && tmp;j++){
        if(a[i][j]=='#')tmp=false;
      }
      if(tmp){
        a.erase(a.begin()+i);
        h--;
        chk = true;
      }
    }
    for(j=0;j<w;j++){
      bool tmp = true;
      for(i=0;i<h;i++){
        if(a[i][j]=='#')tmp=false;
      }
      if(tmp){
        for(i=0;i<h;i++)a[i].erase(a[i].begin()+j);
        w--;
        chk = true;
      }
    }
  }
  for(i=0;i<h;i++){
    for(j=0;j<w;j++)cout<<a[i][j];
    cout<<endl;
  }

}


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

typedef long long ll;

void solve(ll b){
	// 階数全探索
	int res=0,res2=0;
	for(ll i=1;i<=1e8;i++){
		ll p=i*(i+1)/2;
		if(b<p)break;
		if((b-p)%i==0){
			res2=i;
			res=(b-p)/i;
		}
	}
	printf("%d %d\n",res+1,res2);
}


int main(){
	ll b;
	while(cin >> b,b){
		solve(b);
	}
}



Measured memory_bytes: 3224
# -*- coding: utf-8 -*-

from queue import Queue

h,w,n = map(int,input().split())
map = [[0] * w for _ in range(h)]
for i in range(h):
    map[i] = list(input())

que = Queue()
ans = 0
checked = [[-1] * w for _ in range(h)]

def bfs():
    global que,ans,checked
    while not que.empty():
        xy = que.get()
        if xy[0] == g[0] and xy[1] == g[1]:
            ans = checked[xy[1]][xy[0]]
            return
        for i in range(-1,2):
            for j in range(-1,2):
                if i == j or i == -j:
                    continue
                else:
                    if 0 <= xy[0] + i < w and 0 <= xy[1] + j < h:
                        if checked[xy[1]+j][xy[0]+i] == -1 and map[xy[1]+j][xy[0]+i] != "X":
                            checked[xy[1]+j][xy[0]+i] = checked[xy[1]][xy[0]] + 1
                            que.put([xy[0]+i,xy[1]+j])

mark = [[0,0] for _ in range(n+1)]
for i in range(h):
    for j in range(w):
        for k in range(1,n+1):
            if map[i][j] == str(k):
                mark[k] = [j,i]
            elif map[i][j] == "S":
                mark[0] = [j,i]

cnt = 0
for i in range(1,len(mark)):
    que = Queue()
    que.put([mark[i-1][0],mark[i-1][1]])
    g = [mark[i][0],mark[i][1]]
    ans = 0
    checked = [[-1] * w for _ in range(h)]
    checked[mark[i-1][1]][mark[i-1][0]] = 0
    bfs()
    cnt += ans

print(cnt)


Measured memory_bytes: 43384
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <tuple>
#include <functional>

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define irep(i,n) for(int  i = 0; i < n; i++)
#define irep2(i,a,n) for(int i = a; i < n; i++)
#define lrep(i,n) for(long long  i = 0; i < n; i++)
#define lrep2(i,a,n) for(long long i = a; i < n; i++)
#define in(a) cin >> a
#define out(a) cout << a << endl
typedef long long ll;

typedef std::vector<int> v_int;
typedef std::vector<std::vector<int> > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<std::vector<ll> > v2_ll;

using namespace std;

int main() 
{
    int x,a,b;
    cin >> x >> a >> b;

    cout << (x-a)%b << endl;

    return 0;
}
    



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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i];
    if(i == SZ(s)-1) {
      cout << endl;
    } else {
      cout << " ";
    }
  }
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);

  int n; cin >> n;
  if(n == 0 || n == 2) {
    cout << 1 << endl;
  } else if(n == 1) {
    cout << 2 << endl;
  } else {
    cout << 0 << endl;
  }
}



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

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

int main(void)
{
    double ans = 0;
    int n;

    scanf("%d", &n);
    double v[n];
    for (int i = 0; i < n; i++)
        scanf("%lf", &v[i]);

    qsort(v, n, sizeof(double), compare_double);

    ans = (v[0] + v[1]) / 2;
    for (int i = 2; i < n; i++)
        ans = (ans + v[i]) / 2;

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

    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifdef LOCAL
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif

#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;

const long long MOD = 1000000007;

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

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

long long COM(long long n, long long k) {
    long long ue = 1;
    long long shita = 1;
    rep(i, k) {
        ue *= (n - i);
        shita *= (i + 1);
        ue = ue % MOD;
        shita = shita % MOD;
    }
    return ue % MOD * modinv(shita, MOD) % MOD;
}

int main() {
    long long n, a, b;
    cin >> n >> a >> b;
    debug((modpow(2, n, MOD) - 1));
    debug(COM(n, a), COM(n, b));

    long long res = (modpow(2, n, MOD) - 1 - COM(n, a) - COM(n, b));
    if (res < 0) {
        while(res<0){
            res+=MOD;
        }
        cout << res % MOD << endl;
    } else if (res == 0) {
        cout << res << endl;
    } else {
        cout << res % MOD << endl;
    }
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    MOD = 10 ** 9 + 7

    pos = []
    neg = []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)

    flag = False  # 積を正にできるか

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
            
        print(ans % MOD)
        exit()


    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = sorted([abs(x) for x in A])
        for a in A[:K]:
            ans *= a
            ans %= MOD
        ans *= -1
    else:
        pos = sorted(pos)
        neg = sorted(neg, reverse=True)
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos.pop()
            ans %= MOD

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        pairs = []
        while len(pos) >= 2:
            x = pos.pop()
            x *= pos.pop()
            pairs.append(x)
        while len(neg) >= 2:
            x = neg.pop()
            x *= neg.pop()
            pairs.append(x)
        pairs = sorted(pairs, reverse=True)
        for p in pairs[: K // 2]:
            ans *= p
            ans %= MOD

    print(ans % MOD)

    
if __name__ == '__main__':
    main()


Measured memory_bytes: 31784