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

int n,h;
int ans;

struct node{
	int an,bn;
}a[100005];
int b[100005];
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	cin>>n>>h;
	for(int i=1;i<=n;i++)
		cin>>a[i].an>>a[i].bn;
	int maxn=0;
	for(int i=1;i<=n;i++)
		if(a[i].an>maxn) maxn=a[i].an;
	int j=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i].bn>maxn) 
		{
			b[j]=a[i].bn;
			j++;
		}
	}
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<j;i++)
	{
		ans++;
		h-=b[i];
		if(h<=0)
		{
			cout<<ans;
			return 0;
		}
		else continue;
	}
	while(h>0)
	{
		h-=maxn;
		ans++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

const int INF = 1 << 30;
const int dx[] = {0, 1, 0, -1, 0};
const int dy[] = {0, 0, 1, 0, -1};

class State
{
public:
  int sx, sy, gx, gy, time;
  State(int _sx, int _sy, int _gx, int _gy, int _time)
    :sx(_sx), sy(_sy), gx(_gx), gy(_gy), time(_time) {}
};

int main()
{
  int H, W;
  while (cin >> H >> W) {
    if ((H|W) == 0)
      break;

    vector<string> city(H);
    int sx, sy, gx, gy;
    for (int i = 0; i < H; ++i) {
      cin >> city[i];

      if (city[i].find_first_of("A") != string::npos) {
	sy = i;
	sx = city[i].find_first_of("A");
	city[sy][sx] = '.';
      }
      if (city[i].find_first_of("B") != string::npos) {
	gy = i;
	gx = city[i].find_first_of("B");
	city[gy][gx] = '.';
      }
    }

    string pattern;
    cin >> pattern;
    for (int i = 0; i < pattern.size(); ++i) {
      if (pattern[i] == '5')
	pattern[i] = '0';
      else if (pattern[i] == '8')
	pattern[i] = '4';
      else if (pattern[i] == '6')
	pattern[i] = '1';
      else if (pattern[i] == '4')
	pattern[i] = '3';
      else
	pattern[i] = '2';
    }

    bool found = false;
    queue<State> que;
    que.push(State(sx, sy, gx, gy, 0));
    vector<vector<vector<vector<vector<int> > > > > dp(H, vector<vector<vector<vector<int> > > >(W, vector<vector<vector<int> > >(H, vector<vector<int > >(W, vector<int>(pattern.size(), INF)))));
    while (!que.empty()) {
      const State st = que.front();
      que.pop();

      if(st.sx == st.gx && st.sy == st.gy) {
	cout << st.time << " " << st.sy << " " << st.sx << endl;
	found = true;
	break;
      }

      if (dp[st.sy][st.sx][st.gy][st.gx][st.time%pattern.size()] < st.time)
	continue;
      dp[st.sy][st.sx][st.gy][st.gx][st.time%pattern.size()] = st.time;

      for (int d = 0; d < 5; ++d) {
	sx = st.sx + dx[d];
	sy = st.sy + dy[d];
	gx = st.gx + dx[pattern[st.time%pattern.size()]-'0'];
	gy = st.gy + dy[pattern[st.time%pattern.size()]-'0'];

	if (sx < 0 || W <= sx || sy < 0 || H <= sy || city[sy][sx] == '#')
	  continue;

	if (gx < 0 || W <= gx)
	  gx = st.gx;
	if (gy < 0 || H <= gy)
	  gy = st.gy;

	if (dp[sy][sx][gy][gx][(st.time+1)%pattern.size()] > st.time+1) {
	  dp[sy][sx][gy][gx][(st.time+1)%pattern.size()] = st.time+1;
	  que.push(State(sx, sy, gx, gy, st.time+1));
	}
      }

    }

    if (!found)
      cout << "impossible" << endl;
  }
  return 0;
}

Measured memory_bytes: 10000
#include <stdio.h>

int main(void){
    int n ,a[100000],x[10000],i,tmp=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(i=0;i<n;++i){
        if(i%2==0){
            tmp += a[i];
        }else{
            tmp -= a[i];
        }
    }
    x[0] = tmp/2;
    printf("%d ",x[0]*2);
    for(i=1;i<n-1;++i){
        x[i] = a[i-1]-x[i-1];
        printf("%d ",x[i]*2);
    }
    x[n-1] = a[n-2]-x[n-2];
    printf("%d\n",x[n-1]*2);
    return 0;
}

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

using namespace std;

typedef long long LL;

int n,k,a[100005],d,dq;
bool flag=false;
int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	d=a[1];
	for (int i=2;i<=n;++i) d=__gcd(d,a[i]);
	for (int i=1;i<=n;++i) 
	{
		if (a[i]<k) continue;
		dq=a[i]-k;
		if (dq%d==0) flag=true;
	}
	if (flag) printf("POSSIBLE\n");
	else printf("IMPOSSIBLE\n");
	return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <string>
using namespace std;
string minus2(int K){
    if (K==1){
        return "1";
    }
    else if (K==0){
        return "0";
    }
    string S="";
    if (K % 2 != 0){
        S="1";
        K--;
    }
    else{
        S="0";
    }
    K /= -2;
    return minus2(K)+S;
}
int main(void){
    int N;
    cin >> N;
    cout << minus2(N) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define REP(i, a, n) for(int i = (a); i < (n); i++)
using namespace std;

int N, M, B[500], R[500];
vector<int> G[1000];
int match[1000];
bool used[1000];

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

bool dfs(int v) {
  used[v] = true;
  REP(i, 0, G[v].size()) {
    int u = G[v][i], w = match[u];
    if(w < 0 || (!used[w] && dfs(w))) {
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

int main(void) {
  while(cin >> M >> N, M && N) {
    REP(i, 0, M) cin >> B[i];
    REP(i, 0, N) cin >> R[i];
    REP(i, 0, M + N) G[i].clear();
    REP(i, 0, M) REP(j, 0, N) if(gcd(B[i], R[j]) > 1) {
      G[i].push_back(M + j);
      G[M + j].push_back(i);
    }

    int ans = 0;
    REP(i, 0, M + N) match[i] = -1;
    REP(i, 0, M + N) {
      if(match[i] < 0) {
        REP(j, 0, M + N) used[j] = 0;
        if(dfs(i)) ans++;
      }
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 4968
unittest
{
	assert( [ "5 5 7" ].parse.expand.solve == "YES" );
	assert( [ "7 7 5" ].parse.expand.solve == "NO" );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto abc = input.front.split.to!( long[] );
	return tuple( abc );
}

auto solve( long[] abc )
{
	return abc.sort().equal( [ 5, 5, 7 ] ) ? "YES" : "NO";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll GCD(ll a, ll b){ return a ? GCD(b % a, a) : b; }
int main(){
    int h,w,k;
    cin>>h>>w>>k;
    vector<vector<char>> c(h,vector<char>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++) cin>>c[i][j];
    }
    int ans = 0;
    for(int i=0; i<(1<<h); i++){
        vector<bool> hf(h,false);
        for(int k=0; k<h; k++){
            hf[k] = i&(1<<k);
        }
        for(int j=0; j<(1<<w); j++){
            vector<bool> wf(w,false);
            for(int l=0; l<w; l++){
                wf[l] = j&(1<<l);
            }
            int cnt = 0;
            for(int ii=0; ii<h; ii++){
                for(int jj=0; jj<w; jj++){
                    if(hf[ii]||wf[jj]) continue;
                    if(c[ii][jj]=='#') cnt++;
                }
            }
            if(cnt==k) ans++;
            //cout<<cnt<<endl;
        }
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
string str;
void solve()
{
    int i,len=str.length(),ans=0;
    for(i=0;i<len;i++)
        if (str[i]=='1') ans++;
    cout<<ans<<endl;
}
int main()
{
    while(cin>>str)
        solve();
}

Measured memory_bytes: 256
n = int(input())
w = list(map(int,input().split()))

s = sum(w)
s1 = 0
b = 0
for i in w:
    s1 += i
    s -= i
    f = s - s1
    if f < 0:
        f = -f
        if b > f:
            print(f)
        else:
            print(b)
        break
    b = s - s1

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

int main() {
  int k;
  string s;
  cin >> k >> s;
  if(s.size()<=k){
    cout << s << endl;
  }
  else{
    for(int i=0 ; i<k ; i++){
        cout << s.at(i);
    }
    cout << "..." << endl;
  }  
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
static const int64_t mod=1000000007;
int64_t f(int64_t x,int64_t y){
if(y==0)
  return 1;
  else if(y%2==0)
    return (f(x,y/2)*f(x,y/2))%mod;
  else
    return (x*((f(x,y/2)*f(x,y/2))%mod))%mod;
}
int main(){
 int L,R,d;
  cin>>L>>R>>d;
  cout<<(R/d)-((L-1)/d)<<endl;
  return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define hell 1000000007
using namespace std;
void solve()
{
  ll n,m,i,j,k,c=0,y=0,ans=0,a,b;
  string s;
  cin>>n;
  if(n%2==0)
  {
      cout<<-1; return;
  }
  c=7;
  while(c>0)
  {
      y++;
      c*=10LL;
      c+=7LL;
      c%=n;
      if(y>10000000)
      {
          cout<<-1; return;
      }
  }
  if(n==1 or n==7)
  {
      cout<<1; return;
  }
  cout<<y+1;


}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    solve();
}


Measured memory_bytes: 3644
def examA():
    N, A, B = LI()
    if N==1:
        if A==B:
            print(1)
        else:
            print(0)
        return
    ans = (N-2)*max(B-A,0) + 1
    if B<A:
        ans = 0
    print(ans)
    return

def examB():
    S = SI()
    N = len(S)
    cnt = 0
    for i,s in enumerate(S):
        cnt += N-1
        if s=="U":
            cnt += i
        else:
            cnt += (N-i-1)
    ans = cnt
    print(ans)
    return

def examC():
    N, M, q = LI()
    S = [SI()for _ in range(N)]
    Q = [LI()for _ in range(q)]
    S1 = [[0]*(M+1) for _ in range(N+1)]
    S2 = [[0]*(M+1) for _ in range(N+1)]
    S3 = [[0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        now = 0
        for j in range(M):
            now += int(S[i][j])
            S1[i+1][j+1] = S1[i][j+1]+now
    for i in range(N):
        now = 0
        for j in range(M-1):
            if S[i][j]=="1" and S[i][j+1]=="1":
                now += 1
            S2[i+1][j+1] += S2[i][j+1]+now
    for i in range(M):
        now = 0
        for j in range(N-1):
            if S[j][i]=="1" and S[j+1][i]=="1":
                now += 1
            S3[j+1][i+1] += S3[j+1][i]+now
    ans = [0]*q
    #print(S2)
    #print(S3)
    for i in range(q):
        x1, y1, x2, y2 = Q[i]
        #print(x1,y1,x2,y2)
        x1 -= 1; y1 -= 1
        cur = S1[x2][y2] - S1[x1][y2] - S1[x2][y1] + S1[x1][y1]
        cur -= S2[x2][y2-1] - S2[x1][y2-1] - S2[x2][y1] + S2[x1][y1]
        cur -= S3[x2-1][y2] - S3[x1][y2] - S3[x2-1][y1] + S3[x1][y1]
        ans[i] = cur
    for v in ans:
        print(v)
    return

def examD():
    A = I()
    B = I()

    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():

    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
3 4 4 
1101 
0110 
1101 
1 1 3 4 
1 1 3 1 
2 2 3 4 
1 2 2 4 
"""

Measured memory_bytes: 175572
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n;
  cin>>k;
  int ans=0;
  int x[n];
  for(int i=0;i<n;i++){
    cin>>x[i];
    if(k-x[i]<=x[i]) ans+=(k-x[i])*2;
    else ans+=x[i]*2;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(){
  int k;
  scanf("%d",&k);
  char s[101];
  scanf("%s",s);
  if(strlen(s) <= k)
    printf("%s",s);
  else{
    for(int i = 0; i < k; i++)
      printf("%c",s[i]);
    printf("...");
  }
}

Measured memory_bytes: 1736
import java.util.Scanner;
public class Main 
{
	public static void main(String[] args) 
    {
		Scanner scan = new Scanner(System.in);
		long n = scan.nextLong();
		if(n%2==1)
        {
		    System.out.println(0);
		}
		else
        {
		    long total = 0;
		    long x = n/2;
		    while(x>0)
            {
		        x = x/5; 
		        total += x;
		    }
		    System.out.println(total);
		}
	}
}// :)

Measured memory_bytes: 35708
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define floop(i,a,n) for (int i=a;i<n;i++)
#define rfloop(i,a,n) for (int i=n-1;i>=a;i--)
#define mloop(it,x) for(it=x.begin();it!=x.end();it++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((ll)(x).size())
#define cases ll t; cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef unsigned long long int ull;
typedef vector<ll> vec;
typedef pair<ll,ll> pll;
typedef double db;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll mod=1000000007;
ll pm(ll x,ll n) {ll result=1; while(n>0){if(n%2==1) result=((result%mod)*(x%mod))%mod; x=((x%mod)*(x%mod))%mod; n/=2;} return result;}
ll p(ll x,ll n) {ll result=1; while(n>0){if(n%2==1) result=result*x; x=x*x; n/=2;} return result;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll ncr(ll n,ll r) { ll p=1,k=1; if(n-r<r) r=n-r; if(r!=0) {while(r!=0) {p*=n; k*=r; ll temp=gcd(p,k); p/=temp; k/=temp; n--; r--;} } else p=1; return p;}
ll factorial[300000+1];
void fact(ll n) { factorial[0]=1; factorial[1]=1; floop(i,2,n+1) factorial[i] = (i * factorial[i-1]%mod) % mod; }
ll d,coeff1,coeff2; 
void euclid(ll a, ll b) { if(b==0) { d=a; coeff1=1; coeff2=0; } else { euclid(b,a%b); ll temp=coeff1; coeff1=coeff2; coeff2=temp-(a/b)*(coeff2); } }
ll modinv(ll a) { euclid(a,mod); return (coeff1%mod+mod)%mod; }
int prime[1000001]={};
int spf[1000001]={};
void sieve(ll n)
{
	prime[0]=1;
	prime[1]=1;
	for(ll i=2;i*i<=n;i++)
	{
		if(prime[i]==0)
		{
			for(ll j=i*i;j<=n;j+=i)
			{
				prime[j]=1;	
				if(spf[j]==j)
				spf[j]=i;	
			}		
		}
	}
}
/*
vec s(300000,0);
vec si(300000,1);
ll root(ll a)
{
	while(s[a]!=a)
	a=s[a];
	return a;
}
void uni(ll a,ll b)
{
	ll r1=root(a);
	ll r2=root(b);
	if(si[r1]<si[r2])
	{
		s[r1]=s[r2];
		si[r2]+=si[r1];
	}
	else
	{
		s[r2]=s[r1];
		si[r1]+=si[r2];
	}
}
vector<vec > adj(300000);
vec vis(300000,0);
vec dist(300000,0);
void dfs(ll t,ll n)
{
	vis[t]=1;
	floop(i,0,sz(adj[t]))
	{
		if(vis[adj[t][i]]==0)
		{
			dist[adj[t][i]]=dist[t]+1;
			vis[adj[t][i]]=1;
		//	sum[adj[t][i]]=sum[t]+c[t][adj[t][i]];
			dfs(adj[t][i],n);
		}
	}
}*/
struct my_comp
{
	bool operator()(pair<ll,pll> p1, pair<ll,pll> p2)
	{
		if(p1.fi!=p2.fi)
		return p1.fi>p2.fi;
		return p1.se.fi<p2.se.fi;
	}
};
int main()
{
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	ll ans=0;
	while(b<=a)
	{
		b*=2;
		ans+=1;
	}
	//cout<<ans<<" ";
	while(c<=b)
	{
		ans+=1;
		c*=2;
	}
	
	//cout<<ans<<" ";
	if(ans<=k)
	cout<<"Yes\n";
	else
	cout<<"No\n";
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds; //ordered_set : find_by_order(order), order_of_key(key)
//using namespace __gnu_cxx; //crope : append(str), substr(s, e), at(idx)
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll n, a[303030], pv;

ordered_set<p> st1, st2;
ll s1, s2;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=3*n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) s1 += a[i], st1.insert(p(a[i], i));
    for(int i=n+1; i<=3*n; i++) st2.insert(p(a[i], i));
    for(auto it=st2.begin(); ; it++){
        pv++; if(pv > n) break;
        s2 += it->x;
    }
    ll mx = s1 - s2;
    for(int i=n+1; i<=n+n; i++){
        int ord = st2.order_of_key(p(a[i], i)) + 1;
        if(ord <= n){
            s2 -= a[i]; s2 += st2.find_by_order(n)->x;
        }
        st2.erase(p(a[i], i));
        if(a[i] > st1.find_by_order(i-n-1)->x){
            s1 -= st1.find_by_order(i-n-1)->x;
            s1 += a[i];
        }
        st1.insert(p(a[i], i));
        mx = max(mx, s1 - s2);
    }
    cout << mx;
}


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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

int v[maxn];
int dp[110][maxn], pref[110][maxn];
int n, k;

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)cin >> v[i];

    for (int i = 0; i <= n; i++)dp[i][0] = 1, pref[i][0] = 1;
    for (int i = 0; i <= k; i++)pref[0][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            int val = pref[i - 1][j];
            if (j - v[i] >= 1)val -= pref[i - 1][j - v[i] - 1];
            val = (val + MOD) % MOD;
            (dp[i][j] += val) %= MOD;
            if (j)
                pref[i][j] = pref[i][j - 1] + dp[i][j], pref[i][j] %= MOD;
        }
    }
    cout << dp[n][k] << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}



Measured memory_bytes: 160688
N,m,k = (int(i) for i in input().split())
n,mod,x,y = N*m,10**9+7,0,0
fn,fk = [1]*n,[1]*n
for i in range(n-1): fn[i+1] = (fn[i]*(i+2))%mod
def power(n,k):
	if k==1: return n
	elif k%2==0: return power((n**2)%mod,k//2)
	else: return (n*power(n,k-1))%mod
def comb(n,k):
	if n==0 or k==0 or n==k: return 1
	else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
fk[-1] = power(fn[-1],mod-2)
for i in range(2,n+1): fk[-i] = (fk[-i+1]*(n+2-i))%mod
for i in range(N): x+=i*(N-i)*(m**2)
for i in range(m): y+=i*(m-i)*(N**2)
print(comb(n-2,k-2)*(x+y)%mod)

Measured memory_bytes: 18804
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using Graph = vector<vector<int>>;

const int MAX = 8;
Graph g(MAX);

void dfs(int v, vector<bool> &seen, int &ans) {
  bool allSeen = true;
  rep(i, seen.size()) {
    if (!seen[i] && i != v) {
      allSeen = false;
      break;
    }
  }
  if (allSeen) {
    ans++;
    return;
  }

  seen[v] = true;
  for (auto nv : g[v]) {
    if (seen[nv]) continue;
    dfs(nv, seen, ans);
  }
  seen[v] = false;
}

int main() {
  int n, m;
  cin >> n >> m;
  g.assign(n, vector<int>());
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<bool> seen(n, false);
  int ans = 0;
  dfs(0, seen, ans);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
B = input()
lenB = len(B)

cntB = 0
checkB = [0]*lenB
indB = []
for i, b in enumerate(B):
    if b == 'B':
        cntB += 1
        indB.append(i)

dif = 0
i = 0
for j in range(lenB-cntB, lenB):
    dif += j - indB[i]
    i += 1

print(dif)

Measured memory_bytes: 13028
local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, '*'..string.sub(k, i, i)) end local r = io.read local u = table.unpack or unpack return function() return r(u(a)) end end})
read.N = function(N) local t={} for i=1,N do t[i]=read.n() end return t end
string.totable = function(s) local t={} local u=string.sub for i=1,#s do t[i] = u(s, i, i) end return t end
string.split = function(s) local t={} for w in string.gmatch(s, "[^%s]+") do table.insert(t, w) end return (table.unpack or unpack)(t) end
----
local K, X = read.nn()
print(500 * K >= X and "Yes" or "No")

Measured memory_bytes: 636
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

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

    ll ans = 0;

    srep(i,1,n+1){
        if(i % 3 != 0 && i % 5 != 0)ans += i;
    }

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


Measured memory_bytes: 3636
N, H = map(int, input().split(' '))

maxA = 0
bs = []
for _ in range(N):
    a, b = map(int, input().split(' '))
    bs.append(b)
    if maxA < a:
        maxA = a

bs = list(filter(lambda x: maxA < x, bs))
bs.sort()

cnt = 0
while H > 0 and bs:
    cnt += 1
    H -= bs.pop()

if H > 0:
    cnt += H // maxA
    if H % maxA:
        cnt += 1

print(cnt)


Measured memory_bytes: 7836
#!/usr/bin/env python3
import sys


def ff(n):
    n2 = (n+1)/2
    if n2 % 2 == 0:
        return 0
    else :
        return 1

def f(n):
    if n % 2 == 1:
        return ff(n)
    else:
        return ff(n-1)^n



def solve(A: int, B: int):
    print(f(A-1)^f(B))


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
from enum import Enum
from queue import Queue
import collections
import numpy as np


import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

L,R = map(int,input().split())
min = BIG_NUM
if (R/2019 - L/2019)>=1.0:
    print(0)
else:
    for i in range(L,R+1):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if tmp < min:
                min = tmp
            if min == 0:
                break
    print(min)


Measured memory_bytes: 12488
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

void solve()
{
    int r;
    scanf("%d", &r);
    printf("%lld\n", (ll)r*r * 3);
    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}



Measured memory_bytes: 128
N = int(input())

cnt = dict()
maxcnt = 0
for _ in range(N):
    s = input()
    if s not in cnt:
        cnt[s] = 1
    else:
        cnt[s] += 1
    maxcnt = max(maxcnt, cnt[s])

ans = [s for s, c in cnt.items() if c == maxcnt]
ans = sorted(ans)
for s in ans:
    print(s)


Measured memory_bytes: 96088
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
 
class Point{
public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}
 
  Point operator+(Point p){return Point(x+p.x,y+p.y);}
  Point operator-(Point p){return Point(x-p.x,y-p.y);}
  Point operator*(double k){return Point(x*k,y*k);}
  Point operator/(double k){return Point(x/k,y/k);}
 
  double abs(){return sqrt(norm());}
 
  double norm(){return (x*x+y*y);}
};
typedef Point Vector;
 
class Segment{
public:
  Point p1,p2;
  Segment(Point p1,Point p2):p1(p1),p2(p2){}
};
typedef Segment Line;
 
double dot(Vector a,Vector b){return (a.x*b.x+a.y*b.y);}
double cross(Vector a,Vector b){return (a.x*b.y-a.y*b.x);}
 
Point project(Segment s,Point p){
  Vector base=(s.p2-s.p1);
  double r=(dot(p-s.p1,base)/base.norm());
  return (s.p1+base*r);
}
 
int main()
{
  Point A,B,C,D;
  int q;
 
  cin>>A.x>>A.y>>B.x>>B.y;
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>C.x>>C.y;
    D=project(Segment(A,B),C);
    printf("%.10f %.10f\n",D.x,D.y);
  }
  return 0;
}


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

int n,m,f[422][422]; 
char s[21][21];

int turn(int x,int y)
{
	return (x-1)*m+y;
}

int main()
{
//	freopen("data.txt","r",stdin);
//	freopen("my.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
	int t=n*m;
	for(int i=1;i<=t;++i)
		for(int j=1;j<=t;++j)
			f[i][j]=1e9;
	int u,v;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			u=turn(i,j);
			if(s[i][j]=='#')
			{
				if(u>m) f[u][u-m]=1e9;
				f[u][u+m]=f[u][u]=f[u][u-1]=f[u][u+1]=1e9;
				continue;
			}
			f[u][u]=0;
			if(i>1 && s[i-1][j]=='.') f[u][u-m]=1;
			if(i<n && s[i+1][j]=='.') f[u][u+m]=1;
			if(j>1 && s[i][j-1]=='.') f[u][u-1]=1;
			if(j<m && s[i][j+1]=='.') f[u][u+1]=1;
		}
	for(int k=1;k<=t;++k)
		for(int i=1;i<=t;++i)
			for(int j=1;j<=t;++j)
				if(f[i][k]<1e9 && f[k][j]<1e9) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	int ans=0;
	for(int i=1;i<=t;++i)
		for(int j=1;j<=t;++j)
			if(f[i][j]<1e9) ans=max(ans,f[i][j]);
	printf("%d",ans);
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<long long,long long> ii; 	
typedef complex<long double> com;

const ll mod = 1e9+7;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    ld ppi = 3.14159265358;
	ld r;
    cin >> r;
    cout << fixed << setprecision(60) << ld(2)*ppi*r << endl;
}


Measured memory_bytes: 3804
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int n;
# define M_PI           3.14159265358979323846 
void printKoch(int step,double x1,double y1,double x5,double y5) {
	if (step == n) {
		printf("%.8f %.8f\n", x5, y5);
		return;
	}
	double x2 = x5 / 3 + x1 * 2 / 3;
	double y2 = y5 / 3 + y1 * 2 / 3;

	double x4 = x1 / 3 + x5 * 2 / 3;
	double y4 = y1 / 3 + y5 * 2 / 3;

	double th = M_PI * 60.0 / 180.0;
	double x3 = (x4 - x2)* cos(th) - (y4 - y2) * sin(th) + x2;
	double y3 = (x4 - x2)* sin(th) + (y4 - y2) * cos(th) + y2;

	
		printKoch(step+1,x1,y1,x2,y2);
		printKoch(step+1,x2,y2,x3,y3);
		printKoch(step+1,x3,y3,x4,y4);
		printKoch(step+1,x4,y4,x5,y5);
}
int main() {
	cin >> n;
	printf("0.00000000 0.00000000\n");
	printKoch(0,0,0,100,0);
	return 0;
}


Measured memory_bytes: 3184
# B - Buffet

N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]

ans = 0
for i in range(N):
    ans += B[A[i] - 1]
    if i == N - 1:
        break
    if A[i] == A[i + 1] - 1:
        ans += C[A[i] - 1]

print(ans)


Measured memory_bytes: 3064
import heapq
N,K=map(int,raw_input().split())
c=[]
for i in range(N):
	heapq.heappush(c, tuple( map(int,raw_input().split()) ) )

cnt=0
for i in range(len(c)):
	val=heapq.heappop(c)
	cnt+=val[1]
	if K<=cnt:
		print val[0]
		break

Measured memory_bytes: 19584
#include<bits/stdc++.h>
using namespace std;
int arr[1099];
int main()
{
    int i, n;
    double ind = 0.0, mini = 10000000;
    double sum = 0.0;
    cin >> n;
    for(i = 0; i < n; i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
    double avg = sum  / n;
    for(i = 0; i < n; i++)
    {
        double dif = abs(avg - arr[i]);
        if(dif < mini)
        {
            ind = i;
            mini = dif;
        }
    }
    cout << ind << endl;
}


Measured memory_bytes: 256
import copy
H,W,K = map(int,input().split())
ls3 = []
for i in range(H):
    ls1 = input()
    ls2 = [0 if j == '.' else 1 for j in ls1]
    ls3.append(ls2)

ii = 0
for i in range(2**H):
    for j in range(2**W):
        ls4 = copy.deepcopy(ls3)
        for k in range(H):
            for l in range(W):
                if (i>>k & 1):
                    ls4[k][l] = 0
                if (j>>l & 1):
                    ls4[k][l] = 0
        cou = 0
        for ls in ls4:
            cou += ls.count(1)
        if cou == K:
            ii+=1       

print(ii)

Measured memory_bytes: 77736
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node {
  int key;
  struct Node *right,*left,*parent;
};

struct Node *root,*NIL;

void insert(int k){
  struct Node *y=NIL;
  struct Node *x=root;
  struct Node *z;

  z=(struct Node *)malloc(sizeof(struct Node));
  z->key=k;
  z->left=NIL;
  z->right=NIL;
  

  while (x!=NIL){
    y=x;
    if(z->key < x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }

  z->parent = y;
  
  if(y==NIL){
    root=z;
  }
  else{
    if(z->key < y->key){
      y->left=z;
    }
    else{
      y->right=z;
    }
  }
}

void inorder(struct Node *u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(struct Node *u){
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int n,i,x;
  char com[10];

  scanf("%d",&n);
  
  for(i=0 ; i<n ; i++){
    scanf("%s",com);
   
    if(strcmp(com,"insert")==0){
      scanf("%d" ,&x);
      insert(x);
    }
    
    else if(strcmp(com,"print")==0){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    
  }
  
  return 0;
}
     
      
  



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

#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

const int maxn=100005;
int n,s,pos;
int x[maxn];
ll p[maxn],ans;

pll solve(int l,int r){
	if(r<=pos)return mp(s-x[l],s-x[r]);
	if(l>pos)return mp(x[l]-s,x[r]-s);
	if(p[l]>=p[r]){
		p[l]+=p[r];
		pll res=solve(l,r-1);
		return mp(res.fst,res.fst+x[r]-x[l]);
	}
	else{
		p[r]+=p[l];
		pll res=solve(l+1,r);
		return mp(res.snd+x[r]-x[l],res.snd);
	}
}

int main(){
	scanf("%d%d",&n,&s);
	REP(i,n)scanf("%d%lld",&x[i],&p[i]);
	while(pos+1<=n&&x[pos+1]<s)pos++;
	pll ans=solve(1,n);
	printf("%lld\n",max(ans.fst,ans.snd));
	return 0;
}


Measured memory_bytes: 3968
s = input()
k =int(input())

word_lis=set()
n = len(s)
for i in range(n):
    for j in range(i+1,min(i+k+1,n+1)):
        word_lis.add(s[i:j])
word_lis = sorted(list(word_lis))
print(word_lis[k-1])

Measured memory_bytes: 4592
#include <iostream>
#include<algorithm>

using namespace std;

int main()
{
	int w, h, n,i,x,y,a,x1,x2,y1,y2;
	cin >> w >> h >> n;

	x1 = 0, y1 = 0, x2 = w, y2 = h;
	for (i = 0; i < n; i++) {
		cin >> x >> y >> a;
		if (a == 1) {
			if (x1 < x && x2 > x)x1 = x;
			else if (x2 <= x)x1 = 0, x2 = 0;
		}
		else if (a == 2) {
			if (x > x1 && x < x2)
				x2 = x;
			else if (x <= x1) x1 = 0,x2 = 0;
		}
		else if (a == 3) {
			if (y > y1 && y < y2) y1 = y;
			else if (y >= y2)y1 = 0, y2 = 0;
		}
		else if (a == 4) {
			if (y < y2 && y > y1) y2 = y;
			else if (y <= y1) y1 = 0, y2 = 0;
 		}
	}
	x = x2 - x1;
	y = y2 - y1;
	cout << x * y << endl;
	return 0;
}

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

using namespace std;
using namespace atcoder;

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

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "[";
  REP(i, SZ(v)) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << "(" << p.first << " " << p.second << ")";
}

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 (b < a) {
    a = b;
    return true;
  }
  return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;

ll extended_gcd(ll a, ll b, ll &x, ll &y) {
  // solve ax + by = gcd(a, b)
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  ll X, Y;
  ll g = extended_gcd(b, a % b, X, Y);
  x = Y;
  y = X - a / b * Y;
  return g;
}

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

  ll n;
  cin >> n;
  n *= 2;
  ll orn = n;
  map<ll, int> mp;
  for (ll i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      mp[i]++;
      n /= i;
    }
  }

  if (n != 1) mp[n] = 1;
  n = orn;

  vector<pair<ll, int>> v;
  for (auto &e: mp) v.emplace_back(e);
  int sz = SZ(v);
  //cout << v << endl;

  ll mi = LINF;
  function<void(int, int, ll)> dfs = [&](int k, int l, ll a) {
    //cout << k << " " << l << " " << a << endl;
    if (k == sz) {
      ll b = n / a;
      if(__gcd(a, b) != 1) return;
      ll x, y;
      extended_gcd(a, b, x, y);
      if(x == 0) {
        x += b;
        y -= a;
      } else if(y == 0) {
        x -= b;
        y += a;
      }
      /*
      cout << a << " " << b << " " << x << " " << y << endl;
      cout << abs(a * x) << " " << abs(b*y) << endl;
      cout << min(abs(a*x), abs(b*y)) << endl;
      cout << endl;
       */

      chmin(mi, min(abs(a*x), abs(b*y)));
      return;
    }
    if (l == v[k].second) {
      dfs(k + 1, 0, a);
      return;
    }

    dfs(k + 1, 0, a);
    dfs(k, l + 1, a * v[k].first);
  };

  dfs(0, 0, 1);

  cout << mi << endl;

  return 0;
}

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

#define int long long

using namespace std;

#define MOD 1000000007
#define SZ 105


int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        int n,k;
        cin>>n>>k;

        int freq[15]={0};

        for(int i=0;i<k;i++)
        {
                int temp;
                cin>>temp;
                freq[temp]=1;
        }

        while(1)
        {
                int temp=n;
                int foo=0;
                while(temp)
                {
                        int x=temp%10;
                        if(freq[x])
                                foo=1;
                        temp/=10;
                }
                if(foo==0)
                {
                        cout<<n<<endl;
                        return 0;
                }
                n++;
        }


        return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>
#include <set>
#include <sstream>
#include <iomanip>
#include <limits>
#include <cstring>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<string, string> sP;
typedef pair<ll, pair<ll, ll>> PP;

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second



int main() {
	ll h, w, a[310][310], d, q, l, r, rui[200010] = { 0 };
	P it[100000];
	cin >> h >> w >> d;
	for (int i = 0;i < h;i++) {
		for (int j = 0;j < w;j++) {
			cin >> a[i][j];
			it[a[i][j]] = P(i, j);
		}
	}
	for (int i = 1;i <= h*w;i++) {
		rui[i + d] = rui[i] + abs(it[i].fr - it[i + d].fr) + abs(it[i].sc - it[i + d].sc);
	}
	cin >> q;
	for (int i = 0;i < q;i++) {
		cin >> l >> r;
		cout << rui[r] - rui[l] << endl;
	}
	return 0;
}

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

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

  using LL = long long;

  struct Switch {
    int id, x, y, left, right, down, up;
    Switch(int i=-1, int x=-1, int y=-1): id(i), x(x), y(y), left(i), right(i), down(i), up(i) {}
  };

  using Node = tuple<LL, int, int>;
  priority_queue<Node, vector<Node>, greater<Node>> q;
  int S = 0, G = K+1;
  vector<Switch> sw(G+1);
  unordered_map<int, vector<int>> X, Y;

  X[1].push_back(S); Y[1].push_back(S);
  X[M].push_back(G); Y[N].push_back(G);
  sw[S] = Switch(S, 1, 1);
  q.emplace(0, S, 0);
  for(int i = 1; i <= K; ++i) {
    int x, y;
    cin >> x >> y;
    if(x==M && y==N) continue;
    if(x==1 && y==1) {q.emplace(1, S, 1); continue;}
    sw[i] = Switch(i, x, y);
    X[x].push_back(i);
    Y[y].push_back(i);
  }
  sw[G] = Switch(G, M, N);

  for(auto& p: X) sort(begin(p.second), end(p.second), [&](int l, int r) {return sw[l].y < sw[r].y;});
  for(auto& p: Y) sort(begin(p.second), end(p.second), [&](int l, int r) {return sw[l].x < sw[r].x;});
  for(auto& p: X) {
    auto& v = p.second;
    for(int i = 1; i < v.size(); ++i) {
      if(v[i-1] != S) sw[v[i]].down = v[i-1];
      sw[v[i-1]].up = v[i];
    }
  }
  for(auto& p: Y) {
    auto& v = p.second;
    for(int i = 1; i < v.size(); ++i) {
      if(v[i-1] != S) sw[v[i]].left = v[i-1];
      sw[v[i-1]].right = v[i];
    }
  }

  vector<vector<LL>> d(G+1, vector<LL>(2, -1));
  while(!q.empty()) {
    LL t; int i, s;
    tie(t, i, s) = q.top();
    q.pop();

    if(~d[i][s]) continue;
    d[i][s] = t;

    if(i == G) break;

    if(i != S) if(!~d[i][!s]) q.emplace(t+1, i, !s);

    if(s) {
      if(!~d[sw[i].left][s])  q.emplace(t+sw[i].x-sw[sw[i].left].x,  sw[i].left,  s);
      if(!~d[sw[i].right][s]) q.emplace(t+sw[sw[i].right].x-sw[i].x, sw[i].right, s);
    } else {
      if(!~d[sw[i].down][s]) q.emplace(t+sw[i].y-sw[sw[i].down].y, sw[i].down, s);
      if(!~d[sw[i].up][s])   q.emplace(t+sw[sw[i].up].y-sw[i].y,   sw[i].up,   s);
    }
  }

  cout << max(d[G][0], d[G][1]) << endl;
}

Measured memory_bytes: 36764
long M=998244353,D[2][90001],s=1;
N,S,i,j,k;
main(a)
{
	**D=*D[1]=1;
	for(scanf("%*d");~scanf("%d",&a);)
	{
		for(j=S;~j;j--)for(k=2;k--;)D[k][j+a]=(D[k][j+a]+D[k][j])%M,D[k][j]=D[k][j]*-~k%M;
		S+=a;
		s=s*3%M;
	}
	for(int i=-~S/2;i<=S;i++)s=(s-D[1][i]*3%M+M)%M;
	if(~S%2)s=(s+D[0][S/2]*3%M)%M;
	printf("%d",s);
}

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

int main(void){
    
    int N,K,R,S,P;
    char *T;
    int *iT;
    int ans,point;

    scanf("%d %d",&N,&K);
    scanf("%d %d %d",&R,&S,&P);

    T = malloc(sizeof(char)*N + 1);
    iT = malloc(sizeof(int)*N);

    scanf("%s",T);


    for(int i = 0; i < N ; i++){
        switch (T[i])
        {
        case 'r':
            iT[i] = P;
            break;
        case 's':
            iT[i] = R;
            break;
        case 'p':
            iT[i] = S;
            break;
        }
        if(i >= K && T[i] == T[i-K]){
            iT[i] = 0;
            T[i] = '\0';
        }
    }

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

    printf("%d",ans);

    return 0;
}

Measured memory_bytes: 640
use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n = lines.next().unwrap().unwrap().parse::<usize>().unwrap();
    let mut x = Vec::new();
    let mut y = Vec::new();
    for _ in 0..n {
        let x_y = lines.next().unwrap().unwrap();
        let mut x_y = x_y.split_whitespace();
        x.push(x_y.next().unwrap().parse::<f64>().unwrap());
        y.push(x_y.next().unwrap().parse::<f64>().unwrap());
    }

    let mut ans = 0.0;
    for i in 0..n {
        for j in 0..n {
            let d = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
            ans += d.sqrt();
        }
    }
    ans /= n as f64;

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}


int main() {
    int sx,sy,tx,ty;
    cin >> sx >> sy >> tx >> ty;
    for(int i = sx;i<tx;i++) {
        cout << "R";
    }
    for(int i = sy;i<ty;i++) {
        cout << "U";
    }
    for(int i = tx;i>sx;i--) {
        cout << "L";
    }
    for(int i = ty;i>sy;i--) {
        cout <<"D";
    }
    cout << "D";
    for(int i = sx;i<=tx;i++) {
        cout << "R";
    }
    for(int i = sy;i<=ty;i++) {
        cout << "U";
    }
    cout << "L";
    cout << "U";
    for(int i = tx;i>=sx;i--) {
        cout << "L";
    }
    for(int i = ty;i>=sy;i--) {
        cout <<"D";
    }
    cout << "R";
    cout << endl;
}

Measured memory_bytes: 3612
#include <iostream>
using namespace std;
int main(void){
    int n, a[20000];
    cin >> n;
    for(int i=0;i<n;i++){
        a[i] = 50000 * i + 1;
    }
    for(int i=0;i<n;i++){
        int p;
        cin >> p;
        a[p-1] += i+1;
    }
    
    for(int i=0;i<n;i++){
        cout << a[i] << " ";
    }
    cout << endl;
    for(int i=0;i<n;i++){
        cout << 50000 * (n-1-i) + 1 << " ";
    }
    cout << endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
using namespace std;
typedef long long ll;

int main()
{
  int N, K;
  int p[210000];
  double dict[1001];
  cin >> N >> K;

  rep(i,N) cin >> p[i];

  dict[0]=0.0;
  FOR(i,1,1000){
    int sum = i*(i+1)/2;
    dict[i] = (double)sum/(double)i;
  }

  double exp[210000];
  rep(i,N) exp[i] = dict[p[i]];

  double L[210000], R[210000];
  L[0] = 0; R[N] = 0;
  FOR(i, 1, N){
    L[i] = L[i-1] + exp[i-1];
  }
  for(int i=N-1; i>=0; i--){
    R[i] = R[i+1] + exp[i];
  }
  double total = L[N];

  double res = 0;
  for(int i=0; i+K-1<N; i++){
    double ex = total - L[i] - R[i+K];
    res = max(res, ex);
  }

  printf("%.7f\n", res);
}

Measured memory_bytes: 5888
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
//const long long MOD = 1000000007;
const long long MOD = 998244353;
using namespace std;

int main(int argc, char* argv[])
{
    ll n,a,b;
    scanf("%lld%lld%lld", &n, &a, &b);
    if(abs(a-b)%2==0) {
       printf("%lld\n", abs(a-b)/2); 
    }
    else {
        if(a>b) swap(a,b);
        printf("%lld\n", MIN((a+b-1)/2,(n-a+n-b+1)/2));
    }

    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

#define vii vector<int>
#define vip vector<pair<int,int> >
#define pb push_back

int main(int argc,char* argv[])
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //#ifndef ONLINE_JUDGE
    //   freopen("input.txt", "r", stdin);
    //#endif
    int w,h,n;
    cin>>h>>w>>n;
    int ans;
    if(n%max(h,w)==0) ans=n/max(h,w);
    else ans=n/max(h,w)+1;
    cout<<ans;


    return 0;
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

const ll INF = ll(1e18) + 1;

ll N, K;
vector<ll> A;

bool check(ll x) {
    ll total = 0;
    rep(i, N) {
        if (A[i] >= 0) {
            int l = -1, r = N;
            while (r - l > 1) {
                int c = (r + l) / 2;
                if (A[i] * A[c] < x) l = c;
                else r = c;
            }
            total += r;
        } else {
            int l = -1, r = N;
            while (r - l > 1) {
                int c = (r + l) / 2;
                if (A[i] * A[c] < x) r = c;
                else l = c;
            }
            total += N - r;
        }
        if (A[i] * A[i] < x) total--;
    }
    total /= 2;
    return total < K;
}

int main() {
    cin >> N >> K;
    A.resize(N);
    rep(i, N) cin >> A[i];
    sort(A.begin(), A.end());

    ll l = -INF;
    ll r = INF;
    while (r - l > 1) {
        ll c = (r + l) / 2;
        if (check(c)) l = c;
        else r = c;
    }

    cout << l << endl;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define nn '\n'
#define YES cout<<"YES"<<'\n'
#define NO cout<<"NO"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define yes cout<<"yes"<<'\n'
#define no cout<<"no"<<'\n'
void YN(bool flg){cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg){cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define out(n) cout << n << '\n';
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n /= 2; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

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

    int n; cin >> n;
    VI h(n); REP(i,n) cin >> h[i];
    int ans = 0 , tmp = 0;
    int now = h[0];
    FOR(i,1,n){
        if(now>=h[i])tmp++; else tmp = 0;
        chmax(ans,tmp);
        now = h[i];
    }
    out(ans);

    return 0;
}

Measured memory_bytes: 1024