akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<pair<ll,ll> > vii;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<pair<long long,long long> > vpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<ll,pair<ll,ll> > iii;
#define PI 3.141592653589793
#define mod (ll)(1000*1000*1000+7)
//# define N 300005
template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); }
template<typename T> T pow(T a,T b, ll m){T ans=1; while(b>0){ if(b%2==1) ans=((ans%m)*(a%m))%m; b/=2; a=((a%m)*(a%m))%m; } return ans%m; }
# define INF (ll)1e18+5LL
# define LN 20  
typedef pair<ll,pair<ll,ll> > pii;
# define INF1 (int)1e9+2
# define maxn 100006
# define offset 1005

/*************************************************
struct Coupon {
    ll l;
    ll r;
    ll id;

    Coupon(ll l, ll r, ll id): l(l), r(r), id(id) {} // Initialization

    bool operator<(const Coupon& c) { // Sorting
        return l < c.l;    
    }
};

**************************************************/
int main()
{
  int n,t;
  cin >> n >> t;
  set<ll>s;
  ll cnt=0;
  ll a[n];
  for(int i=0;i<n;i++)
  {
     cin >> a[i];
  }
  s.insert(a[0]);
  ll md=0;
  for(int i=1;i<n;i++)
  {
    ll min1=(*s.begin());
    ll diff=(a[i]-min1);
    if(diff>md)
    {
      md=diff;
      cnt=1;
    }
    else if(md==diff)
    {
       cnt++;
    }
    s.insert(a[i]);
  }
  cout << cnt;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i < b; i++)
typedef long long ll;
typedef std::vector<int> vi;

using namespace std;

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

    string s;
    cin >> s;
    int n = s.size();
    string t = s;
    if (s[n - 1] == 's') {
        t.append("es");
    }
    else {
        t.append("s");
    }
    
    cout << t << "\n";

    return 0;
}

Measured memory_bytes: 3664
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
#from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, k, q = Is()
A = [I()-1 for _ in range(q)]
score = [k-q]*n

for a in A:
    score[a] += 1

for i in range(n):
    if score[i]>0:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 56280
N,M = map(int,input().split())
guess_list = [-1]*N
if N ==1:
    for i in range(M):
        s,c = map(int,input().split())
        if guess_list[s-1] != -1 and guess_list[s-1] != c:
            print('-1')
            break
        else:
            guess_list[s-1] = c
    else:
        if guess_list[0] == -1:
            guess_list[0] = 0
        print(guess_list[0])
else:
    for i in range(M):
        s,c = map(int,input().split())
        if guess_list[s-1] != -1 and guess_list[s-1] != c:
            print('-1')
            break
        elif s == 1 and c == 0:
            print('-1')
            break
        else:
            guess_list[s-1] = c
    else:
        for i in range(N):
            if guess_list[i] == -1:
                if i == 0:
                    guess_list[i] = 1
                else:
                    guess_list[i] = 0
        guess_list = map(str,guess_list)
        print(''.join(guess_list))

    

Measured memory_bytes: 3064
#include<stdio.h>
#include<vector>
#include<stdlib.h>
#define pb push_back
using namespace std;

int H;
int c[100005],C[100005],L[100005],R[100005],g[100005],M[100005],V[100005];
vector<int> r[100005],X[100005];

void f(int x, int h)
{
    int i;
    H=max(H,h);
    c[x]++;
    X[h].pb(x);
    for(i=0;i<r[x].size();i++){
        if(c[r[x][i]])continue;
        g[r[x][i]]=x;
        f(r[x][i],h+1);
    }
}

void G(int x)
{
    int i;
    L[x]=-1e9,R[x]=1e9;
    if(C[x]){
        L[x]=R[x]=C[x]-1;
        return;
    }
    for(i=0;i<r[x].size();i++){
        if(r[x][i]==g[x])continue;
        L[x]=max(L[x],L[r[x][i]]-1);
        R[x]=min(R[x],R[r[x][i]]+1);
        if(M[x]==0)M[x]=M[r[x][i]];
        else if(M[r[x][i]]&&M[x]!=M[r[x][i]]){
            printf("No\n");
            exit(0);
        }
    }
    if(M[x])M[x]=3-M[x];
    if(L[x]>R[x]){
        printf("No\n");
        exit(0);
    }
}

void h(int x)
{
    int i,nx;
    for(i=0;i<r[x].size();i++){
        nx=r[x][i];
        if(nx==g[x])continue;
        if(L[nx]<=V[x]-1&&V[x]-1<=R[r[x][i]])V[nx]=V[x]-1;
        else if(L[nx]<=V[x]+1&&V[x]+1<=R[r[x][i]])V[nx]=V[x]+1;
        else{
            printf("No\n");
            exit(0);
        }
        h(nx);
    }
}

int main()
{
    int n,k,s,e,i,x,v;
    scanf("%d", &n);
    for(i=1;i<n;i++){
        scanf("%d %d", &s, &e);
        r[s].pb(e);
        r[e].pb(s);
    }
    scanf("%d", &k);
    for(i=1;i<=k;i++){
        scanf("%d %d", &x, &v);
        C[x]=v+1;
    }
    f(1,1);
    while(H){
        for(i=0;i<X[H].size();i++)G(X[H][i]);
        H--;
    }
    V[1]=L[1];
    h(1);
    printf("Yes\n");
    for(i=1;i<=n;i++){
        printf("%d\n", V[i]);
    }
    return 0;
}


Measured memory_bytes: 19328
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int gcd(int n, int m) {
    if (n < m) swap(n, m);
    while (m != 0) {
        int r = n % m;
        n = m;
        m = r;
    }
    return n;
}

struct Sieve {
    Sieve(int n) : l(n + 1, 0) {
        for (int i = 2; i <= n; i++) {
            if (!l[i]) p.push_back(l[i] = i);
            for (int q : p) {
                if (q > l[i]) break;
                if (int j = i * q; j <= n) l[j] = q; else break;
            }
        }
    }
    bool is_prime(int i) {
        return l[i] == i;
    }
    vector<int> l, p;
};

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

    int n;
    cin >> n;

    Sieve si((int)1e6);
    vector<char> b((int)1e6 + 1, 0);
    int x = 0, y = 0;

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

        x = gcd(x, a);

        while (a > 1) {
            int t = si.l[a];
            if (b[t]) {
                y = 1;
                break;
            }
            while (a % t == 0) a /= t;
            b[t] = 1;
        }
    }

    int r = 2;
    if (x == 1) {
        r = y;
    }

    const char *c[3] = { "pairwise coprime", "setwise coprime", "not coprime" };
    cout << c[r] << endl;

    return 0;
}

Measured memory_bytes: 8460
// https://atcoder.jp/contests/abc150/tasks/abc150_c
// AtCoder Beginner Contest 150
// C - Count Order

/*
Problem.
大きさNの順列について、並びかえたP,Qが与えられる。
Pが辞書順a番目、Qが辞書順b番目として|a-b|は？

Point.
next_permutationを使えば辞書順に順列を生成してくれる。
*/

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<ctime>

using namespace std;
using ll = long long;

bool match(int n, vector<int> v, vector<int> p){
  for(int i = 0; i < n; i++){
    if(v[i] != p[i]) return false;
  }
  return true;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  int n; cin >> n;
  vector<int> v(n);
  for(int i = 0; i < n; i++) v[i] = i+1;
  vector<int> p(n);
  vector<int> q(n);
  for(auto &i:p) cin >> i;
  for(auto &i:q) cin >> i;
  int a = 0, b = 0, cnt = 0;
  do{
    cnt++;
    if(match(n, v, p)) a = cnt;
    if(match(n, v, q)) b = cnt;
  }while(next_permutation(v.begin(), v.end()));
  cout << abs(a - b) << endl;
  // end-----------------------------------------------
  cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
#define PI 3.141592653589793



int main(){
  int h, w; cin >> h >> w;
  string S[h];
  rep(i, h){
    cin >> S[i];
  }
  int dp[h][w];
  rep(i, h){
    rep(j, w){
      dp[i][j] = inf;
    }
  }
  if(S[0][0]=='#') dp[0][0] = 1;
  else dp[0][0] = 0;
  rep(i, h){
    rep(j, w){
      if(i>=1 && S[i-1][j]=='.' && S[i][j]=='#') dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
      else if(i>=1)  dp[i][j] = min(dp[i][j], dp[i-1][j]);
      if(j>=1 && S[i][j-1]=='.' && S[i][j]=='#') dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
      else if(j>=1)  dp[i][j] = min(dp[i][j], dp[i][j-1]);
    }
  }
  cout << dp[h-1][w-1] << endl;
}

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

int n, m, a[60], b[60], c[60], d[60];

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		int ans = 0;
		int dis = abs(a[i] - c[0]) + abs(b[i] - d[0]);
		for (int j = 1; j < m; j++) {
			if (dis > abs(a[i] - c[j]) + abs(b[i] - d[j])) {
				dis = abs(a[i] - c[j]) + abs(b[i] - d[j]);
				ans = j;
			}
		}
		cout << ans + 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int iinf = 1 << 28;
const long long llinf = 1ll << 60;
const double PI = 3.14159265;

void work() {
   int n; cin>>n;
   if (n%2 == 0) {
       cout << (n>>1) << endl;
   } else {
       cout << (n>>1) + 1 << endl;
   }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    work();

    return 0;
}


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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  else if (A + B == C + D) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main(){
    int k; cin >> k;
    dunk(a[k-1]);
}

Measured memory_bytes: 256
import sys
f = sys.stdin

def triangle_area(a, b, c):
    z = (a + b + c) / 2
    s = (z * (z - a) * (z - b) * (z - c)) ** 0.5
    return s

apexes = []
for line in f:
    x, y = map(float, line.split(','))
    apexes.append(x + y * 1j)

s = 0
for i in range(2,len(apexes)):
    s += triangle_area(abs(apexes[0] - apexes[i - 1]),abs(apexes[0] - apexes[i]),abs(apexes[i] - apexes[i - 1]))
print(s)

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

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

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

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

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

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


int main(){
  int N;
  string S;

  cin >> N >> S;

  S = '$' + S;

  int ans = 0;
  for (int i=0; i<N; i++) {
    ans += S[i] != S[i+1];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

string f(string n) {
    for (int i = 0; i < n.size(); i++) {
        if (n[i] == '1') {
            n[i] = '9';
        } else if (n[i] == '9') {
            n[i] = '1';
        }
    }
    return n;
}

int main() {

    string n;
    cin >> n;

    string result = f(n);
    cout << result << endl;

    return 0;
}


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

int main () {
    long long n;
    while (scanf("%lld", &n) == 1) {
        n--;
        int len = 1;
        long long p = 26;
        while (p <= n) {
            n -= p;
            p *= 26;
            len++;
        }
        string name(len, '-');
        int i = len - 1;
        while (i >= 0) {
            name[i] = n % 26 + 'a';
            n /= 26;
            i--;    
        }
        printf("%s\n", name.c_str());
    }
}



Measured memory_bytes: 3684
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define N 17
#define NN 34567
#define NNN 15671000
typedef long long ll;
template<typename T> inline void read(T &x) {
	x = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
using namespace std;
const int P = 1e9 + 7;
ll mi[N * N];
int n, m, All;
int e[N][N];
int ecnt[N][NN];//ecnt[i][s] : i -> s
inline void init() {
	mi[0] = 1;
	for (int i = 1; i <= m; ++i)	mi[i] = (mi[i - 1] << 1) % P;
	for (int i = 0; i < n; ++i) {
		for (int s = 0; s <= All; ++s) {
			for (int j = 0; j < n; ++j) if ((s >> j) & 1) {
				ecnt[i][s] += e[i][j];
			}
		}
	}
}
inline ll calc1(int s, int t) {
	ll res = 1;
	for (int i = 0; i < n; ++i) if ((s >> i) & 1) {
		res = 1ll * res * mi[ecnt[i][t]] % P;
	}
	return res;
}
inline ll calc2(int s, int t) {
	ll res = 1;
	for (int i = 0; i < n; ++i) if ((s >> i) & 1) {
		res = 1ll * res * (mi[ecnt[i][t]] - 1) % P;
	}
	return res;
}
int f[NNN];
inline void work() {
	f[0] = 1;
	for (int s = 1; s <= All; ++s) if ((s & 1) == ((s >> 1) & 1)) {
		for (int t = s; t; t = (t - 1) & s) {
			f[s] = (f[s] + 1ll * calc1(t, s ^ t) * calc2(s ^ t, t) % P * f[s ^ t] % P) % P;
		}
	}
	ll ans = (mi[m] - f[All]) % P;
	printf("%lld\n", (ans % P + P) % P);
}
int main() {
	read(n), read(m); All = (1 << n) - 1;
	for (int i = 1; i <= m; ++i) {
		int u, v; read(u), read(v);
		--u; --v;
		e[u][v] = 1;
	}
	init();
	work();
	return 0;
}


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

using namespace std;
typedef long long ll;
#define rep(i,j,n) for (int i = j; i < (n); i++)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<int,int>P;
const ll mod=1e9+7;
const ll INF = 1e9;

int main(){

  int a,b;cin>>a>>b;

  if(b==1){out(0);return 0;}
  if(a>=b){out(1);return 0;}
  rep(i,2,50){
    if(a*i-(i-1)>=b){out(i);return 0;}
  }

  return 0;
}


Measured memory_bytes: 256
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
      int a=sc.nextInt();
      int b=sc.nextInt();
      int c=sc.nextInt();
      if((b-a+2)/2<=c){
      	for(int i=a;i<=b;i++)System.out.println(i);
      }
      else   {
      for(int i=a;i<=a+c-1;i++)System.out.println(i);for(int i=b-c+1;i<=b;i++)System.out.println(i);
      }
    }
}


Measured memory_bytes: 21844
//O7Oo7oO7O

#include <bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

using ll = long long int;

int main()
{
	IOS
	
    int n;
    cin>>n;
    string s;
    cin>>s;
    int len=s.size();
    vector<int> r,g;
    unordered_map<int,int> b;
    for(int i=0;i<len;i++)
    {
    	if(s[i]=='R')
    		r.push_back(i);
    	else if(s[i]=='G')
    		g.push_back(i);
    	else
    		b[i]=1;
    }
    ll cnt=((ll)r.size())*((ll)g.size())*((ll)b.size());
    for(int i=0;i<(int)r.size();i++)
    {
    	for(int j=0;j<(int)g.size();j++)
    	{
    		if((r[i]+g[j])%2==0 && b[(r[i]+g[j])/2]==1)
    			cnt--;
    		if(b[2*r[i]-g[j]])
    			cnt--;
    		if(b[2*g[j]-r[i]])
    			cnt--;
    	}
    }
    cout<<cnt<<"\n";
    


    return 0;
}



Measured memory_bytes: 4088
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#include <iomanip>
//cout << fixed << setprecision(20) << *** << endl;
#define rep(i,N) for(int i=0;i<(int)N;++i)
typedef long long ll;
using namespace std;
int main()
{
	ll A,B,M,t;
	vector<ll>AA,BB,ANS;
	cin>>A>>B>>M;
	rep(i,A){
		cin>>t;
		AA.push_back(t);
	}
	rep(i,B){
		cin>>t;
		BB.push_back(t);
	}
	rep(i,M){
		ll x,y,z,zz;
		cin>>x>>y>>z;
		zz=AA[x-1]+BB[y-1]-z;
		ANS.push_back(zz);
	}
	sort(AA.begin(),AA.end());
	sort(BB.begin(),BB.end());
	ANS.push_back(AA[0]+BB[0]);
	sort(ANS.begin(),ANS.end());
	cout<<ANS[0]<<endl;
}

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
using ll = long long;
using namespace std;

int n; ll k;
vector<ll> a;
vector<ll> f;

bool possible( ll x ){
  ll sum = 0;
  for( int i = 0; i < n; ++i ){
    sum += max(0ll, a[i]-x/f[i]);
  }
  return sum <= k;
}

int main(){
  cin >> n >> k;
  for( int i = 0; i < n; ++i ){
    ll t; cin >> t;
    a.push_back(t);  
  }
  for( int i = 0; i < n; ++i ){
    ll t; cin >> t;
    f.push_back(t);  
  }
  sort(a.begin(), a.end());
  sort(f.begin(), f.end(), greater<ll>());
  ll ok = 1e18;
  ll ng = -1;
  while( abs(ok-ng) > 1 ){
    ll m = (ok+ng)/2;
    if( possible(m) ){
      ok = m;
    } else {
      ng = m;
    }
  }
  cout << ok << endl;
}

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

#define FOR(i,l,r) for(int i = int(l);i < int(r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N,Q,A,B;
const int MAX_N = 1 << 18;
int X [MAX_N];
const ll INF = 1e18;
struct SegmentTree{
	vector<ll> dat,lazyAdd;
	SegmentTree(){
		dat.assign(MAX_N * 2,INF);
		lazyAdd.assign(MAX_N * 2,0);
	}
	void push(int idx){
		if(lazyAdd [idx] == 0) return;
		lazyAdd [idx * 2 + 1] += lazyAdd [idx];
		dat [idx * 2 + 1] += lazyAdd [idx];
		lazyAdd [idx * 2 + 2] += lazyAdd [idx];
		dat [idx * 2 + 2] += lazyAdd [idx];
		lazyAdd [idx] = 0;
	}
	void fix(int idx){
		dat [idx] = min(dat [idx * 2 + 1],dat [idx * 2 + 2]);
	}
	void update(int a,int b,ll val,int idx = 0,int l = 0,int r = MAX_N){
		if(b <= l || r <= a) return;
		if(a <= l && r <= b){
			if(dat [idx] + lazyAdd [idx] > val){
				dat [idx] = val;
				lazyAdd [idx] = 0;
			}
			return;
		}
		push(idx);
		update(a,b,val,idx * 2 + 1,l,(l + r) / 2);
		update(a,b,val,idx * 2 + 2,(l + r) / 2,r);
		fix(idx);
	}
	void rangeAdd(int a,int b,ll val,int idx = 0,int l = 0,int r = MAX_N){
		if(b <= l || r <= a) return;
		if(a <= l && r <= b){
			dat [idx] += val;
			lazyAdd [idx] += val;
			return;
		}
		push(idx);
		rangeAdd(a,b,val,idx * 2 + 1,l,(l + r) / 2);
		rangeAdd(a,b,val,idx * 2 + 2,(l + r) / 2,r);
		fix(idx);
	}
	ll getMin(int a,int b,int idx = 0,int l = 0,int r = MAX_N){
		if(b <= l || r <= a) return INF;
		if(a <= l && r <= b) return dat [idx];
		push(idx);
		ll res = getMin(a,b,idx * 2 + 1,l,(l + r) / 2);
		chmin(res,getMin(a,b,idx * 2 + 2,(l + r) / 2,r));
		fix(idx);
		return res;
	}
};
SegmentTree st1,st2;

int main()
{
	scanf("%d%d%d%d",&N,&Q,&A,&B);
	A--; B--;
	FOR(i,0,Q){
		scanf("%d",&X [i]);
		X [i]--;
	}

	st1.update(A,A + 1,abs(X [0] - B) + A);
	st1.update(B,B + 1,abs(X [0] - A) + B);
	st2.update(A,A + 1,abs(X [0] - B) + (N - 1) - A);
	st2.update(B,B + 1,abs(X [0] - A) + (N - 1) - B);
	FOR(i,1,Q){
		ll x = st1.getMin(X [i],MAX_N) - X [i];
		ll y = st2.getMin(0,X [i]) - (N - 1) + X [i];
		st1.rangeAdd(0,MAX_N,abs(X [i] - X [i - 1]));
		st2.rangeAdd(0,MAX_N,abs(X [i] - X [i - 1]));
		st1.update(X [i - 1],X [i - 1] + 1,min(x,y) + X [i - 1]);
		st2.update(X [i - 1],X [i - 1] + 1,min(x,y) + (N - 1) - X [i - 1]);
	}

	ll ans = INF;
	FOR(i,0,N){
		chmin(ans,st1.getMin(i,i + 1) - i);
	}
	printf("%lld\n",ans);

	return 0;
}


Measured memory_bytes: 17408
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
using vl=vector<ll>;
using vb=vector<bool>;
using vs=vector<string>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
const ll oo =0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define FOR(i,a,b) for(ll i=(a); i<(b); i++)
#define FORD(i,a,b) for(ll i=ll(b)-1;i>=(a);i--)
#define TR(X) ({if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })
long long binom(int n, int k) {
    long long bin = 1;
    if (k > n-k) k = n-k;
    for (int i = 1; i <= k; i++) {
	bin *= n--;
	bin /= i;
    }
    return bin;
}

int main(){ cin.sync_with_stdio(0);
    ll N; cin >> N;
    ll P; cin >> P;

    ll gerade = 0;
    ll ungerade = 0;

    FOR(i, 0, N) {
	ll v; cin >> v;
	if (v%2) ungerade ++;
	else gerade ++;
    }

    ll cnt_gerade = 0;
    FOR(i, 0, gerade+1) {
	for (int j = 0; j <= ungerade; j+= 2) {
	    cnt_gerade += binom(gerade, i) * binom(ungerade, j) ;
	}
    }

    ll cnt_ungerade = 0;
    for (int i = 1; i <= ungerade; i+= 2) {
	FOR(j, 0, gerade+1) {
	    cnt_ungerade += binom(ungerade, i) * binom(gerade, j);
	}
    }

    if (P) cout << cnt_ungerade << endl;
    else cout << cnt_gerade << endl;
} //cin.tie(0) bei schnellem Wechseln


Measured memory_bytes: 256
N=int(input())
s=list(input())
a=[0 for i in range(N)]
west=0
east=0
for i in range(N):
    a[i]+=west
    if s[i]=="W":
        west+=1
for i in range(N-1,-1,-1):
    a[i]+=east
    if s[i]=="E":
        east+=1
print(min(a))

Measured memory_bytes: 19532
#include<cstdio>
#include<vector>

using namespace std;

int main(){
	int a, b, c, d, e, f; scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f);
	a *= 100; b *= 100;
	vector<int> w, s;
	for(int i = 0; i <= f / 100; i++) for(int j = 0; j <= f / 100; j++){
		if(a * i + b * j <= f) w.push_back(a * i + b * j);
	}
	for(int i = 0; i <= f; i++) for(int j = 0; j <= f; j++){
		if(c * i + d * j <= f) s.push_back(c * i + d * j);
	}
	int res1 = -1, res2;
	for(int i = 1; i < w.size(); i++) for(int j = 0; j < s.size(); j++){
		if(w[i] + s[j] > f) continue;
		if(w[i] * e < 100 * s[j]) continue;
		if(res1 < 0 || res1 * s[j] > res2 * (w[i] + s[j])) { res1 = w[i] + s[j]; res2 = s[j]; }
	}
	printf("%d %d\n", res1, res2);
	return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin >> n;
  vector<ll> a(n);
  for(int i = 0;i < n;i++)cin >> a[i];
  sort(a.begin(),a.end());

  ll a_1,a_2;
  a_1 = a[n-1];
  a_2 = a[0];

  if(n % 2 == 0){
    ll cent = a_1/2;
    ll now_dist = abs(cent - a_2);
    for(int i = 0;i < n-1;i++){
      ll dist = abs(a[i] - cent);
      if(dist < now_dist){
        now_dist = dist;
        a_2 = a[i];
      }
    }
  }
  else{
    ll cent_1 = a_1/2;
    ll cent_2 = (a_1+1)/2;
    ll now_dist = abs(cent_1 - a_2) + abs(cent_2 - a_2);
    for(int i = 0;i < n-1;i++){
      ll dist = abs(cent_1 - a[i]) + abs(cent_2 - a[i]);
      if(dist < now_dist){
        a_2 = a[i];
        now_dist = dist;
      }
    }
  }

  cout << a_1 << " " << a_2 << endl;
}


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

int main() {
  //定義一覧
  int N = 0;
  int l = 0;
  int r = 0;
  int tmp = 0;
  
  //繰り返しの数の入力
  cin >> N;
  //繰り返し
  for(int i = 0; i < N; i++){
  	//団体様の数の入力
    cin >> l >> r;
    //団体数の算出
    tmp += r - l + 1;
  }
  
  //出力
  cout << tmp << endl;
}

Measured memory_bytes: 256
#include<iostream>	// 入出力
#include<stdio.h>	// printf()が使える小数は%fで
#include<math.h>	// 数学の関数
#include<vector>	// 配列
#include<string>	// 文字列
#include<map>		// 連想配列
#include<stack>		// スタック
#include<queue>		// キュー
#include<algorithm> // ソートとか

using namespace std;


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

	vector<vector<int>> tree(N);

	for (int i = 0; i < N - 1; ++i)
	{
		int a, b; cin >> a >> b;

		tree[a - 1].emplace_back(b - 1);
		tree[b - 1].emplace_back(a - 1);
	}


	vector<int> T(N, -1);
	queue<int> Q;

	Q.push(0);
	T[0] = 0;

	while (!Q.empty()) {

		int u = Q.front();
		Q.pop();

		for (int v : tree[u]) {

			if (T[v] == -1) {

				T[v] = u;

				Q.push(v);

			}

		}
	}


	vector<int> root;

	int sech = N - 1;
	root.emplace_back(N - 1);
	while (sech != T[sech])
	{
		sech = T[sech];

		root.emplace_back(sech);
	}

	int bar = root[root.size() / 2];


	int sunuke = 1;
	vector<bool> used(N, false);

	stack<int> S;

	S.push(N - 1);
	used[N - 1] = true;

	while(!S.empty())
	{
		int v = S.top();
		S.pop();

		for (int u : tree[v])
		{
			if (!used[u] && u != bar)
			{
				S.push(u);
				used[u] = true;
				sunuke += 1;
			}
		}
	}

	//cout << sunuke << endl;

	if (N % 2 == 0) {
		if (sunuke >= N / 2) {
			cout << "Snuke" << endl;
		}
		else
		{
			cout << "Fennec" << endl;
		}
	}
	if (N % 2 == 1) {
		if (sunuke > N / 2) {
			cout << "Snuke" << endl;
		}
		else
		{
			cout << "Fennec" << endl;
		}
	}



	return 0;
}

Measured memory_bytes: 6780
#include<bits/stdc++.h>
 
using namespace std;
int main()
{
  string s;
  cin>>s;
  for(int i=0;i<4;i++)cout << s[i];
  cout << " ";
  for(int i=4;i<12;i++)cout << s[i];
  cout << endl;
  return 0;
}

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

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n]; int[] G = new int[n];
		int[] GL = new int[n]; int[] GR = new int[n];

		for(int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sc.next());
		}
      
      		Arrays.parallelSort(a);

		GL[0] = 0; GR[n-1] = 0;

		for(int i = 1; i < n; i++) {
			GL[i] = gcm(GL[i-1], a[i-1]);
			GR[n-i-1] = gcm(GR[n-i],a[n-i]);
		}

		for(int i =0; i < n; i++)
			G[i] = gcm(GR[i],GL[i]);

		Arrays.parallelSort(G);

		System.out.println(G[n-1]);

		sc.close();
	}

	public static int gcm(int a, int b) {
		if(a == 0 || b == 0) return Math.max(a, b);
		if(a < b)  {
			return gcm(b, a);
		}else {
			if(a%b == 0) {
				return b;
			}else {
				return gcm(b, a%b);
			}
		}
	}
}

Measured memory_bytes: 47316
import std.stdio;
import std.string;
import std.conv;
import std.bigint;
import std.typecons;
import std.algorithm;
import std.array;
 
void main() {
    auto tmp = readln.split.to!(int[]);
    auto N = tmp[0];
    auto M = tmp[1];
    writeln((M * 1900 + (N-M) * 100) * 2^^M);
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

using Weight=long long;
static const Weight INF=1LL<<57;

struct Edge {
    size_t src, dst;
    Weight weight;
    Edge() {}
    Edge(size_t src, size_t dst, Weight weight=1):
        src(src), dst(dst), weight(weight)
    {}
};

bool operator<(const Edge &e, const Edge &f) {
    if (e.weight != f.weight) {
        return e.weight > f.weight;
    } else {
        return e.src!=f.src? e.src<f.src : e.dst<f.dst;
    }
}

using Edges=vector<Edge>;
using Vertex=vector<Edge>;
using Graph=vector<Vertex>;

void join(Graph &g, size_t s, size_t d, Weight w=1) {
    // non-directed
    g[s].push_back(Edge(s, d, w));
    g[d].push_back(Edge(d, s, w));
}

void connect(Graph &g, size_t s, size_t d, Weight w=1) {
    // directed
    g[s].push_back(Edge(s, d, w));
}

void visit(
    const Graph &g, size_t v, size_t u, map<size_t, size_t> &artpoint,
    vector<size_t> &num, vector<size_t> &low, int &time
) {
    low[v] = num[v] = ++time;
    for (const Edge &e: g[v]) {
        size_t w=e.dst;
        if (!num[w]) {
            visit(g, w, v, artpoint, num, low, time);
            low[v] = min(low[v], low[w]);

            if (num[v]==1? num[w]!=2 : low[w]>=num[v])
                ++artpoint[v];

        } else {
            low[v] = min(low[v], num[w]);
        }
    }
}

map<size_t, size_t> get_artpoint(const Graph &g) {
    const size_t V=g.size();

    vector<size_t> low(V), num(V);
    map<size_t, size_t> artpoint;
    for (size_t u=0; u<V; ++u) if (!num[u]) {
        int time=0;
        visit(g, u, -1, artpoint, num, low, time);
    }

    return artpoint;
}

int main() {
    size_t V, E;
    scanf("%zu %zu", &V, &E);

    Graph g(V);
    for (size_t i=0; i<E; ++i) {
        size_t s, t;
        scanf("%zu %zu", &s, &t);

        join(g, s, t);
    }

    map<size_t, size_t> artpoint=get_artpoint(g);

    for (pair<const size_t, size_t> v: artpoint)
        printf("%zu\n", v.first);

    return 0;
}

Measured memory_bytes: 7572
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String s = sc.next();
        String[] ss = s.split("");
        int x = 0;
        int answer = 0;
        for(int i = 0;i<n;i++){
            if(ss[i].equals("D")){
                x--;
            }else{
                x++;
                answer = Math.max(answer,x);
            }
        }
        System.out.println(answer);
    }
}

Measured memory_bytes: 21844
import java.util.Scanner;
class Main
{
    public static void main(String args[])
    {
	Scanner scan=new Scanner(System.in);
	while(true)
	    {
		int x,h;
		x=scan.nextInt();
		h=scan.nextInt();
		if(x==0 && h==0)break;
		double ans,length;
		length=Math.sqrt(Math.pow((double)x/2,2)+Math.pow((double)h,2));
		ans=Math.pow((double)x,2)+2*(((double)x*length));
		System.out.printf("%.6f\n",ans);
	    }
    }
}

Measured memory_bytes: 17196
def check_p(p):
    global k, ws
    ct, nt = 0, 1
    for w in ws:
        if ct + w <= p:
            ct += w
        else:
            nt += 1
            if nt > k:
                return False
            ct = w
    return True


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

ws = [int(input()) for _ in range(n)]
l, r, p = max(ws), sum(ws), 0

while l < r:
    p = (l + r) // 2
    if check_p(p):
        r = p
    else:
        l = p = p + 1

print(p)

Measured memory_bytes: 11596
#pragma region

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define _rep3(i, begin, end) for (register int i = (begin), i##_end = (end); i < i##_end; i++)
#define _irep3(i, begin, end) for (register int i = (end)-1, i##_begin = (begin); i >= i##_begin; i--)
#define _rep2(i, n) _rep3(i, 0, n)
#define _irep2(i, n) _irep3(i, 0, n)
#define _overload3(_1, _2, _3, name, ...) name
#define rep(...) _overload3(__VA_ARGS__, _rep3, _rep2, )(__VA_ARGS__)
#define irep(...) _overload3(__VA_ARGS__, _irep3, _irep2, )(__VA_ARGS__)
#define out(x) cout << (x) << '\n';
#define debug(x) cerr << #x << " = " << (x) << " (line: " << __LINE__ << ") " << endl;

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vvb = vector<vector<bool>>;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &pair) {
  cin >> pair.first >> pair.second;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[ ";
  rep(i, vec.size()) i == 0 ? os << vec[i] : os << ", " << vec[i];
  os << " ]";
  return os;
}

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

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

void init() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(16);
}

#pragma endregion

#define MOD 1000000007
#define INF 2147483647

void frac(vvb &a, int N, int M, int y = 0, int x = 0) {
  if (N == 1 && M == 1) {
    a[y][x] = 1;
    return;
  }
  if (N == 1) {
    frac(a, N, M - 1, y, x);
    frac(a, N, M - 1, y, x + (1 << M - 1));
    return;
  }
  if (M == 1) {
    frac(a, N - 1, M, y, x);
    frac(a, N - 1, M, y + (1 << N - 1), x);
    return;
  }
  frac(a, N - 1, M - 1, y, x);
  frac(a, N - 1, M - 1, y + (1 << N - 1), x);
  frac(a, N - 1, M - 1, y, x + (1 << M - 1));
  frac(a, N - 1, M - 1, y + (1 << N - 1), x + (1 << M - 1));
  a[y + (1 << N - 1) - 1][x + (1 << M - 1) - 1] = 1;
}

int main() {
  init();

  int N, M;
  cin >> N >> M;
  int H = (1 << N) - 1, W = (1 << M) - 1;
  vvb a(H, vb(W, 0));
  frac(a, N, M);
  rep(i, H) {
    rep(j, W) cout << a[i][j];
    cout << '\n';
  }
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n == 0) return 1;

    ll res = modpow(x, n/2);
    if(n%2 == 0) return res*res%mod;
    else return res*res%mod*x%mod;
}

ll power(ll x, ll n){
    if(n == 0) return 1;

    ll res = power(x, n/2);
    if(n%2 == 0) return res*res;
    else return res*res*x;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

/* <--------------------------------------------> */

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

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

    // 男性はi番目まで見てすでにペアになった女性の集合がSであるような場合の数(ペアは中のいい人どうし)
    // vector<vector<ll>> dp(n+5, vector<ll>(1<<22, 0));
    // dp[0][0] = 1;
    // for(int i=1; i<n+1; ++i) for(int S=0; S<1<<n; ++S){
    //     // i番目の男の人がj番目の女の人とペアになった？
    //     for(int j=0; j<n; ++j) if((S>>j)&1 && a[i-1][j]==1){
    //         dp[i][S] = (dp[i][S]+dp[i-1][S^(1<<j)])%mod;
    //     } 
    // }
    // O(2^n*n^2) TLE :(

    // すでにペアになった女の集合がSならば、bitcount(S)人目の男までチェックしたとなる
    vector<ll> dp(1<<23, 0);
    dp[0] = 1;
    for(int S=1; S<1<<n; ++S){
        int i=0;
        for(int j=0; j<25; ++j) if(S&1<<j) ++i;
        for(int j=0; j<n; ++j) if(S&1<<j && a[i-1][j]==1) dp[S]=(dp[S]+dp[S^(1<<j)])%mod;
    }

    cout << dp[(1<<n)-1] << endl;


	return 0;
}


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

using namespace std;

long long a[200000];

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

	int n;
	cin >> n;
	for(int i = 0; i < n; i++)cin >> a[i];
	long long ret = a[n - 1];
	bool ok = true;
	if(a[0] != 0)ok = false;
	for(int i = 1; i < n; i++)
	{
		if(a[i] - a[i - 1] > 1)ok = false;
		if(a[i] <= a[i - 1])ret += a[i - 1];
	}
	if(ok)cout << ret << endl;
	else cout << -1 << endl;

	return 0;
}


Measured memory_bytes: 1792
// 明らかに最大のやつに引っ張られる
// それ以外のやつは最大のやつの合間にはさめばいいので、max(A)-1<=max(A)以外の合計、ならばいける
// いけない場合はmax(A)-1-max(A)以外の合計かな
package main

import "fmt"

var k, t int

func main() {
	fmt.Scan(&k, &t)
	max_a := -1
	for i := 0; i < t; i++ {
		var j int
		fmt.Scan(&j)
		if j > max_a {
			max_a = j
		}
	}
	sum := k - max_a
	if max_a-1 <= sum {
		fmt.Println(0)
	} else {
		fmt.Println(max_a - 1 - sum)
	}
}


Measured memory_bytes: 1772
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 5) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    N, M, K = map(int, input().split())
    mod = 998244353
    c = cmbs(mod)
    r = 0
    for i in range(K+1):
        r += pow(M-1, N-1-i, mod) * c.cmb(N-1, i)
    r *= M
    r %= mod
    return r
print(main())


Measured memory_bytes: 109748
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define int long long
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
int MOD=1e9+7;
int pow(int a,int b,int m){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}
int modinv(int k){
	return pow(k,MOD-2,MOD);
}
int ncr(int n,int c){
	int t=1;
	c=min(c,n-c);
	for(int i=1;i<=c;i++){
	 	t=(t*(n-i+1))%MOD;
		t=(t*modinv(i))%MOD;
	}
	return t;
}
signed main(){
	int n,a,b;
	cin>>n>>a>>b;
	int ans=pow(2,n,MOD);
//	cout<<ans<<endl;
	ans=(ans-ncr(n,a)+n*MOD)%MOD;
	ans=(ans-ncr(n,b)+n*MOD)%MOD;
	ans=(ans-1+MOD)%MOD;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>

using namespace std;

string alpha = "abcdefghijk";
vector<string> ans;
int N;

void setTree(int num,string str,int max){
  if(str.length() >= max){
    ans.push_back(str);
    return;
  }
  //numは今まで使った種類の数である
  for(int i=0;i<num;i++){
    //cout<< alpha[i] << ":" << max <<endl;
    setTree(num,str+alpha[i],max);
  }
  //cout << num << endl;
  //新たに文字を追加
  setTree(num+1,str+alpha[num],max);
  return;
}

int main(void){
  cin >> N;
  setTree(1,"a",N);
  for(int i=0;i<ans.size();i++){
    cout << ans[i] << endl;
  }
  return 0;
}



Measured memory_bytes: 7796
#include <bits/stdc++.h>
using namespace std;
int main(){
  int r;
  cin>>r;
  if(r<1200){
    cout<<"ABC"<<endl;
  }
  else if(r>=1200&&r<2800){
    cout<<"ARC"<<endl;
  }
  else if(r>=2800){
    cout<<"AGC"<<endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int n;
  int answer;

  while(scanf("%d",&n)!=EOF){
    answer=0;
    for(int a=0;a<=9;a++){
        for(int b=0;b<=9;b++){
            for(int c=0;c<=9;c++){
                for(int d=0;d<=9;d++){
                    if((a+b+c+d)==n){answer++;}
                }
            }
        }
    }
    printf("%d\n",answer);
  }
        return 0;
}



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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(10);

}

signed main() {
	string s;
	ll ans = INF;

	cin >> s;

	REP(i, s.size() - 2) {
		ans = min(ans, abs(753 - stoll(s.substr(i, 3))));
	}

	cout << ans << endl;
}

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

#define pii pair<int, int>

const int maxN = 1 << 18 | 5, mod = 1e9 + 7;

int H, L;
int res[maxN + 1], ans[maxN + 1];
int w[maxN + 1];

vector<pii> vec[maxN + 1];

inline void update(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }

int main()
{
	scanf("%d ", &H);
	L = 1 << H - 1;
	for(int i = 1; i <= L; i++)
	{
		int x = L + i - 1, p;
		scanf("%d", &p);
		p = L + p - 1;
		while(x) vec[x].push_back( pii(L + i - 1, p) ), x >>= 1;
		w[L + i - 1] = L + i - 1;
	}
	for(int x = L - 1; x >= 1; x--)
	{
		for(int i = 0; i < vec[x].size(); i++)
		{
			int u = vec[x][i].first, v = vec[x][i].second;
			int tp = 1;
			while(v)
			{
				tp = 1ll * tp * v % mod;
				update(ans[x], 1ll * w[u] * x % mod * res[v] % mod * tp % mod);
				update(ans[x], mod - 1ll * w[u] * x % mod * res[v] % mod * tp % mod * v % mod * (v >> 1) % mod);
				v >>= 1;
			}
			v = vec[x][i].second; tp = 1;
			while(v) 
			{
				update(res[v], 1ll * w[u] * tp % mod);
				tp = 1ll * tp * v % mod;
				v >>= 1;
			}
		}
		for(int i = 0; i < vec[x].size(); i++)
		{
			int u = vec[x][i].first, v = vec[x][i].second;
			while(v) res[v] = 0, v >>= 1;
			w[u] = 1ll * w[u] * x % mod;
		}
	}
	int last = 0;
	for(int x = 1; x < L; x++)
	{
		update(ans[x], mod - 1ll * x * (x << 1) % mod * ans[x << 1] % mod);
		update(ans[x], mod - 1ll * x * (x << 1 | 1) % mod * ans[x << 1 | 1] % mod);
		update(last, ans[x]); 
	}
	printf("%d\n", last);
	return 0;
}


Measured memory_bytes: 35132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[100005];
int main() {
    scanf("%s",s+1);
    int n=strlen(s+1);
    if (s[n]=='1'||s[1]=='0'||s[n-1]=='0') {
        puts("-1");
        return 0;
    }
    int now=2;
    while (now<=n-now) {
        if (s[now]!=s[n-now]) {
            puts("-1");
            return 0;
        }
        now++;
    }
    int rt=2,num=1; //num为边的编号
    now=2; //点的编号
    puts("2 1\n");
    while (now<=n-now) {
        if (s[now]=='1') {
            printf("%d %d\n",++now,rt);
            rt=now;
        }
        else {
            printf("%d %d\n",++now,rt);
        }
        num++;
    }
    for (int i=num+1; i<n; i++) printf("%d %d\n",rt,++now);

    return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef pair<int,int> P;
int w,h,c;
int ans;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int dfs(vector<vector<int> > f){
	queue<P> que;
	int fc=f[0][0];
	que.push(P(0,0));
	int a=0;
	vector<vector<bool> > used(h,vector<bool>(w,false));
	while(!que.empty()){
		P t=que.front();
		que.pop();
		if(used[t.first][t.second])
			continue;
		a++;
		used[t.first][t.second]=true;
		for(int i=0;i<4;i++){
			P nt=P(t.first+dy[i],t.second+dx[i]);
			if(nt.first>=0&&nt.first<h&&nt.second>=0&&nt.second<w&&fc==f[nt.first][nt.second]&&!used[nt.first][nt.second]){
				que.push(nt);
			}
		}
	}
	return a;
}
vector<vector<int> > change(vector<vector<int> > f,int col){
	queue<P> que;
	int fc=f[0][0];
	que.push(P(0,0));
	vector<vector<bool> > used(h,vector<bool>(w,false));
	while(!que.empty()){
		P t=que.front();
		que.pop();
		if(used[t.first][t.second])
			continue;
		f[t.first][t.second]=col;
		used[t.first][t.second]=true;
		for(int i=0;i<4;i++){
			P nt=P(t.first+dy[i],t.second+dx[i]);
			if(nt.first>=0&&nt.first<h&&nt.second>=0&&nt.second<w&&fc==f[nt.first][nt.second]&&!used[nt.first][nt.second]){
				que.push(nt);
			}
		}
	}
	return f;
	
}
void ret(vector<vector<int> > f,int cnt){
	if(cnt==5){
		if(f[0][0]==c)
			ans=max(dfs(f),ans);
		return;
	}
	for(int i=1;i<=6;i++){
		if(f[0][0]==i)
			continue;
		ret(change(f,i),cnt+1);
	}
}
int main(){
	while(cin>>h>>w>>c,w||h||c){
		ans=0;
		vector<vector<int> > f(h,vector<int>(w));
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin>>f[i][j];
			}
		}
		ret(f,0);
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 920
//abc149_d.cpp
//Sun Jan 12 11:24:51 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,k,r,s,p;
	cin >> n >> k >> r >> s >> p;
	string t;
	cin >> t;

	int ans = 0;
	int score[3];
	score[0] = r;
	score[1] = s;
	score[2] = p;

	int kachi[n];
	fill(kachi,kachi+n,-1);
	int kaeta[k];
	fill(kaeta,kaeta+k,0);
	for (int i=0;i<n;i++){
		if (t[i]=='r'){
			kachi[i] = 2;
		}else if (t[i]=='s'){
			kachi[i] = 0;
		}else {
			kachi[i] = 1;
		}
		ans += score[kachi[i]];
		if (i>=k){
			if (kachi[i]==kachi[i-k]){
				if (kaeta[i%k]==0){
					ans = ans - score[kachi[i]];
					kaeta[i%k] = 1;
				}else {
					kaeta[i%k] = 0;
				}
			}else {
				kaeta[i%k] = 0;
			}
		}
//		cout << ans << endl;
	}
	cout << ans << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    int n;
    cin >> n;
    ll dp[n]={};
    map<int,int> c;
    rep(i,n){
        int x;
        cin >> x;
        if(c.count(x) && c[x]!=i-1)dp[i]+=dp[c[x]];
        if(i!=0)dp[i]+=dp[i-1];
        else dp[i]=1;
        c[x]=i;
        dp[i]%=mod;
    }
    cout << dp[n-1];
}

Measured memory_bytes: 11136