akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
using namespace std;
#define _GLIBCXX_DEBUG
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define vit vector<lint>::iterator
#define all(x) (x).begin(),(x).end()
#define rep(x) for(int i = 0;i < (x);i++)
#define repj(x) for(int j = 0;j < (x);j++)
#define REP(i,x) for(int (i) = 0;(i) < (x);(i)++)
#define rrep(x) for(int i = (x);i >= 0;i--)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define mod 1000000007
#define graph_set(n) struct edge{int to,int cost;} vector<edge> G((n))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define range(x,y) ((x) >= 0 && (x) < h && (y) >= 0 && (y) < w)
#define pyes cout << "Yes" << endl
#define pno cout << "No" << endl
#define fin return 0
typedef vector<long long> vi;
typedef vector<pair<long long, long long>> vp;
typedef vector<vector<long long>> vvi;
typedef pair<long long, long long> pi;
typedef long long lint;
typedef long long ll;
lint qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
lint qp(ll a, ll b, int mo) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
lint gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
long long INF = 1e19;

int r[100], l[100];
int a, b;

#define MAX 9223372036854775807
/*********************** */

int main() {
	ll s; cin >> s;
    if(s == qp(10,18)){
        cout << 0 <<" " << 0 << " " << qp(10,9) << " " << 0 << " " << 0 <<" " << qp(10,9) << endl;
        return 0;
    }
	ll a, b, c, d;
	b = qp(10, 9) - (s % qp(10, 9));
	c = 1;
	a = qp(10, 9);
	d = (b + s) / a;
	cout << 0 <<" " << 0 << " " << a << " " << b << " " << c  <<" " << d << endl;
  //  cout << a*d - b*c - s << endl;
	return 0;

}

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

const int mod = 1000000007;
// const int mod = 998244353;

struct mint
{
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint &operator+=(const mint m)
    {
        if((x += m.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator-=(const mint m)
    {
        if((x += mod - m.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator*=(const mint m)
    {
        (x *= m.x) %= mod;
        return *this;
    }
    mint operator+(const mint m) const
    {
        return mint(*this) += m;
    }
    mint operator-(const mint m) const
    {
        return mint(*this) -= m;
    }
    mint operator*(const mint m) const
    {
        return mint(*this) *= m;
    }
    mint pow(ll n) const
    {
        if(!n) return 1;
        mint m = pow(n>>1);
        m *= m;
        if(n & 1) m *= *this;
        return m;
    }
    mint inv() const { return pow(mod-2);}
    mint &operator/=(const mint m) { return *this *= m.inv();}
    mint operator/(const mint m) const { return mint(*this) /= m;}
};
istream &operator>>(istream &is, mint &m) { return is >> m.x;}
ostream &operator<<(ostream &os, const mint &m) { return os << m.x;}

struct combination
{
    vector<mint> fact, ifact;
    combination(int n) : fact(n+1), ifact(n+1)
    {
        assert(n < mod);
        fact.at(0) = 1;
        for(int i=1; i<=n; i++)
        {
            fact.at(i) = fact.at(i-1) * i;
        }
        ifact.at(n) = fact.at(n).inv();
        for(int i=n; i>=1; i--)
        {
            ifact.at(i-1) = ifact.at(i) * i;
        }
    }
    mint operator()(int n, int k)
    {
        if(k < 0 || k > n) return 0;
        return fact.at(n) * ifact.at(k) * ifact.at(n-k);
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N+1);
    for(int i=0; i<N+1; i++)
    {
        cin >> A[i];
        A[i]--;
    }

    int left=0, right=0;
    {
        vector<int> indexes(N+1, -1);
        for(int i=0; i<N+1; i++)
        {
            if(indexes[A[i]]==-1) indexes[A[i]] = i;
            else
            {
                left = indexes[A[i]];
                right = i;
            }
            
        }
    }
    combination comb(N+1);
    for(int i=1; i<=N+1; i++)
    {
        mint ans = comb(N+1, i);
        ans -= comb(left-1+N+1-right, i-1);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 5052
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 205, M = N * N * 2, inf = 1e9 + 7 ;
using namespace std ;

int H, W, n, Ax, Bx, Ay, By, s, t, e, ter[M], nxt[M], lnk[N], w[M], rec[M], opt[N], dis[N], cur[N] ;
char a[N][N] ;
void add(int x, int y, int z1, int z2) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e, w[e] = z1, rec[e] = e + 1 ;
	ter[++ e] = x, nxt[e] = lnk[y], lnk[y] = e, w[e] = z2, rec[e] = e - 1 ;
}
bool bfs() {
	rep(i, 1, n) dis[i] = inf ;
	int he = 0, ta = 1 ;
	opt[1] = s, dis[s] = 0 ;
	for ( ; he != ta ; ) {
		int u = opt[++ he] ;
		for (int i = lnk[u] ; i; i = nxt[i]) if (w[i] && dis[ter[i]] == inf) {
			dis[ter[i]] = dis[u] + 1 ;
			opt[++ ta] = ter[i] ;
		}
	}
	return dis[t] < inf ;
}
int dfs(int p, int sum) {
	int res = 0 ;
	if (p == t) return sum ;
	for (int i = cur[p] ; i; i = nxt[i]) if (w[i] && dis[ter[i]] == dis[p] + 1) {
		int tmp = dfs(ter[i], min(w[i], sum - res)) ;
		w[i] -= tmp, w[rec[i]] += tmp, res += tmp ;
		if (w[i]) cur[p] = i ;
		if (sum == res) return res ;
	}
	if (!res) dis[p] = - 1 ;
	return res ;
}
int dinic() {
	int ret = 0 ; 
	for ( ; bfs() ; ) {
		rep(i, 1, n) cur[i] = lnk[i] ;
		ret += dfs(s, inf) ;
	}
	return ret ;
}
int main() {
	scanf("%d%d", &H, &W) ;
	rep(i, 1, H) scanf("%s", a[i] + 1) ;
	n = H + W ; 
	rep(i, 1, H) rep(j, 1, W) {
		if (a[i][j] == 'S') add(i, H + j, inf, inf), Ax = i, Ay = j ;
		if (a[i][j] == 'T') add(i, H + j, inf, inf), Bx = i, By = j ;
	}
	if (Ax == Bx || Ay == By) { puts("-1") ; return 0 ; }
	s = Ax, t = Bx ;
	rep(i, 1, H) rep(j, 1, W) if (a[i][j] == 'o') add(i, H + j, 1, 1) ;
	printf("%d\n", dinic()) ;
	return 0 ; 
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <deque>
#include <string.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;

ll a[7];

int main(){
  REP(i, 7) cin >> a[i];

  ll ans = a[0] / 2 * 2 + a[1] + a[3] / 2 * 2 + a[4] / 2 * 2;
  if(a[0] % 2 == 1 &&  a[3] % 2 == 1 &&  a[4] % 2 == 1) ans += 3;
  else if (a[0] % 2 + a[3] % 2 + a[4] % 2 == 2 && a[0] > 0 && a[3] > 0 && a[4] > 0) ans += 1;

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 256
import sys


class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
        self.u = n

    def root(self, x):
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        self.u -= 1
        return True

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.d[self.root(x)]

    def num_union(self):
        return self.u


input = sys.stdin.readline
while True:
    W, H = map(int, input()[:-1].split())
    if W == 0:
        break
    S = [input()[:-1].split() for _ in [0]*H]

    uf = UnionFind(H*W)
    cnt = 0
    for h, ss in enumerate(S):
        for w, s in enumerate(ss):
            if s == '0':
                cnt += 1
                continue

            if h and w and S[h-1][w-1] == '1':
                uf.unite(h*W+w, (h-1)*W+w-1)
            if h and S[h-1][w] == '1':
                uf.unite(h*W+w, (h-1)*W+w)
            if h and w+1<W and S[h-1][w+1] == '1':
                uf.unite(h*W+w, (h-1)*W+w+1)
            if w and S[h][w-1] == '1':
                uf.unite(h*W+w, h*W+w-1)


    print(uf.u-cnt)



Measured memory_bytes: 5668
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_set>

using namespace std;

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

  int cur = a;
  unordered_set<int> rem;
  if (a % b == c) {
    cout << "YES" << endl;
    return 0;
  }
  rem.insert(a % b);

  while (true) {
    cur += a;
    if (cur % b == c) {
      cout << "YES" << endl;
      return 0;
    } else if (rem.find(cur % b) != rem.end()) {
      cout << "NO" << endl;
      return 0;
    }
    rem.insert(cur % b);
  }
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>

using  namespace std;

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

const int N = 1055;
const int M = 1e6 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

int a[N][N][2],pref[N][N][2],n,k;

void make_pref(){
    for(int col = 0;col < 2;col++){
        for(int i = 0;i<k;i++){
            int cur = 0;
            for(int j = 0;j<k;j++){
                cur += a[i][j][col];
                pref[i][j][col] = cur;
                if(i) pref[i][j][col] += pref[i - 1][j ][col];
            }
        }
    }
}

int get(int x1,int x2,int yy1,int y2,int col){
    if(x2 < x1 || yy1 > y2) return 0;
    int sol = pref[x2][y2][col];
    if(x1) sol -= pref[x1 - 1][y2][col];
    if(yy1) sol -= pref[x2][yy1 - 1][col];
    if(x1 && yy1) sol += pref[x1 - 1][yy1 - 1][col];
    return sol;
}

int obradi_toc(int x,int y,int col){
    int nx = x % k;
    int ny = y % k;
    int ch = x / k + y / k;
    if(ch&1) col = !col;
    a[nx][ny][col]++;
}

int solve(){
    make_pref();
    int sol = 0;
    for(int i = 0;i<k;i++){
        for(int j = 0;j<k;j++){
            sol = max(sol, get(0, i, 0, j, 0) + get(i + 1, k - 1, j + 1 ,k - 1, 0) + get(0, i, j + 1, k - 1, 1) + get(i + 1, k - 1, 0, j , 1));
            sol = max(sol, get(0, i, 0, j, 1) + get(i + 1, k - 1, j + 1 ,k - 1, 1) + get(0, i, j + 1, k - 1, 0) + get(i + 1, k - 1, 0, j , 0));
        }
    }
    return sol;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i = 0;i<n;i++){
        int x,y;
        char c;
        scanf("%d%d %c",&x,&y,&c);
        obradi_toc(x, y, int(c == 'W'));
    }
    printf("%d\n",solve());
}


Measured memory_bytes: 17152
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;

const int MAX=1<<17,mod=1e9+7;

int main() {
	int a,b;
	scanf("%d%d",&a,&b);
	puts(a*b%2==1 ? "Odd" : "Even");
	return 0;
}


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

int main() {
  int64_t N, A, B;
  cin >> N >> A >> B;
  cout << ((N-N%(A+B))/(A+B))*A+min((N%(A+B)),A) << endl;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7,INF=1e17;
const int iINF=1e9;
bool comp(int a,int b){
    return a<b;
}
int main(){
    int n,diff=0;
    cin>>n;
    vector<int>p(n),q(n);
    for(int i=0;i<n;i++)cin>>p[i];
    q=p;
    sort(q.begin(),q.end(),comp);
    for(int i=0;i<n;i++){
        if(p[i]!=q[i]){
            diff++;
        }
    }
    if(diff>2)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    

}

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

typedef long long ll;

int main() {
    int K, T;
    cin >> K >> T;
    vector<int>a(T);
    for (int i = 0; i < T; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    if (T == 1) {
        cout << K -1 << endl;
    } else {
        int total = 0;
        for (int i = 1; i < T; i++) {
            total += a[i];
        }
        if (a[0] <= total) {
            cout << 0 << endl;
        } else {
            cout << a[0] - total - 1 << endl;
        }
    }
}


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

int n, w;
int W[100];
int V[100];

long long int dp[100001];

int main(){
  scanf("%d%d", &n, &w);
  for(int i = 0; i < n; i++) scanf("%d%d", W+i, V+i);

  for(int i = 0; i <= 100000; i++) dp[i] = (1ULL << 62) - 1;

  dp[0] = 0;
  for(int i = 1; i <= n; i++){
    for(int j = 100000; j >= V[i-1]; j--){
      dp[j] = std::min(dp[j], dp[j-V[i-1]] + W[i-1]);
    }
  }

  for(int j = 100000; j >= 0; j--){
    if(dp[j] <= w){
      printf("%d\n", j);
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 896
#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);
    ll s,n;
    cin >> s >> n;
    for (int z=0;z<n;z++){
        ll temp;
        cin >> temp;
        s -= temp;
    }
    cout << max(ll(-1),s) << endl;
}

Measured memory_bytes: 3656
S=input()
n=len(S)
flag=0
S1=S[0:(n-1)//2]
S2=S[(n+2)//2:]
if S1==S1[::-1] and S2==S2[::-1] and S==S[::-1]:
    pass
else:
    flag=1
print('Yes' if flag==0 else 'No')

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

int main() {
	int x;
	int i = 1;
	do {
		cin >> x;
		if (x == 0 || x > 10000)break;
		cout << "Case " << i << ": " << x << endl;
		i++;
	} while (i <= 10000);
	return 0;
}


Measured memory_bytes: 3100
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;


int main() {
  int x, y, a, b, c;
  cin >>x >> y >> a >> b >> c;
  vi p(a), q(b), r(c);
  rep(i, a) cin >> p[i];
  rep(i, b) cin >> q[i];
  rep(i, c) cin >> r[i];

  sort(p.begin(), p.end(), greater<int>());
  sort(q.begin(), q.end(), greater<int>());
  sort(r.begin(), r.end(), greater<int>());

  int p_idx = x-1;
  int q_idx = y-1;

  rep(i, c){
    if (p[p_idx] < q[q_idx]){
      if (p[p_idx] < r[i]){
        p[p_idx] = r[i];
        p_idx = max(p_idx-1, 0);
      }
    }else{
      if (q[q_idx] < r[i]){
        q[q_idx] = r[i];
        q_idx = max(q_idx-1, 0);
      }
    }
  }
  ll ans = 0;
  rep(i, x){
    ans += p[i];
  }
  rep(i, y){
    ans += q[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define ll long long
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define N 300005
#define M 1000000007
#define pii pair<ll,ll>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
main()
{
    int n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    ll sum=a[n-1];
    ll baki=n-2;
    ll now=n-2;
    int c=2;
    while(baki>0)
    {
        sum+=a[now];
        c--;
        if(c==0)
        {
            now--;
            c=2;
        }
        baki--;
    }

    cout<<sum;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int A[303],S;
ll mo=998244353;

ll from[300*301][2];
ll to[300*301][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	from[0][0]=from[0][1]=1;
	ll ret=1;
	FOR(i,N) {
		cin>>A[i];
		S+=A[i];
		ret=ret*3%mo;
		ZERO(to);
		FOR(j,300*301) {
			if(from[j][0]) {
				// add
				(to[j+A[i]][0]+=from[j][0])%=mo;
				// non
				(to[j][0]+=from[j][0])%=mo;
			}
			if(from[j][1]) {
				// add
				(to[j+A[i]][1]+=from[j][1])%=mo;
				// non
				(to[j][1]+=2*from[j][1])%=mo;
			}
		}
		swap(from,to);
	}
	
	
	for(i=0;i<=S;i++) {
		if(i*2>=S) {
			ret-=from[i][1]*3;
		}
		if(i*2==S) {
			ret+=from[i][0]*3;
		}
		ret%=mo;
	}
	cout<<(ret+mo)%mo<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 3072
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int W = scan.nextInt();
        int H = scan.nextInt();
        int x = scan.nextInt();
        int y = scan.nextInt();
        int r = scan.nextInt();

        if(-100 <= x && x <= 100 && -100 <= y && y <= 100){
            if(0 < W && W <= 100 && 0 < H && H <= 100 && 0 < r && r <= 100){

                if(x >= r && (W-x) >= r && (H-y) >= r && y >= r){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
         
            }
        }

    }
}



Measured memory_bytes: 26384
// 22
/****************************************************
https://searleser97.gitlab.io/algorithms/template.cpp
****************************************************/

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fors(_, x, n, s) for (int _ = x; _ < n; _ += s)
#define forn(_, x, n) fors(_, x, n, 1)
#define rep(_, n) forn(_, 0, n)
#define forrs(_, x, n, s) for (int _ = x; _ > n; _ -= s)
#define forrn(_, x, n) forrs(_, x, n, 1)
#define rrep(_, n) forrn(_, n - 1, -1)
#define fi first
#define se second
#define pb push_back
#define pairii pair<int, int>
#define all(x) x.begin(), x.end()
#define cerr(s) cerr << "\033[48;5;196m\033[38;5;15m" << s << "\033[0m"
// typedef __int128_t lli;
typedef long long int li;
typedef long double ld;
// 12
const int inf = 1e9 + 10;
void _main(int tc) {
  int n, k;
  cin >> n >> k;
  assert(n >= 2);
  vector<int> h(n);
  rep(i, n) cin >> h[i];
  vector<int> mem(n, inf);
  mem[n - 1] = 0;
  mem[n - 2] = abs(h[n - 2] - h[n - 1]);

  function<int(int)> fcost = [&](int i) -> int {
    if (mem[i] != inf) return mem[i];
    mem[i] = (1 << 30);
    forn(j, i + 1, (i + 1) + min(k, n - 1 - i)) {
      mem[i] = min(mem[i], abs(h[i] - h[j]) + fcost(j));
    }
    return mem[i];
  };
  cout << fcost(0) << endl;

  // rrep(i, n - 2) {
  //   forn(j, i + 1, (i + 1) + min(k, n - 1 - i)) {
  //     mem[i] = min(mem[i], abs(h[i] - h[j]) + mem[j]);
  //   }
  // }
  // cout << mem[0] << endl;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  _main(0);
  return 0;
  int tc;
  cin >> tc;
  rep(i, tc) _main(i + 1);
}

Measured memory_bytes: 10368
#include <stdio.h>

int main()
{
    int apple;
    int piecesOfApple;

    scanf("%d %d", &apple, &piecesOfApple);

    int cut = apple * 3;

    piecesOfApple >= 2 || apple >= 1 ? printf("%d", (cut + piecesOfApple) / 2) : printf("0");
    
    return 0;
}

Measured memory_bytes: 1732
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define MAX_D 210
#define MAX_N 210

int D, N;
int T[201];
int A[201], B[MAX_N], C[MAX_N];
bool suit[MAX_D][MAX_N];
int dp[MAX_D][MAX_N];

int main() {
    int i, j, k;
    
    scanf("%d%d", &D, &N);
    for (i = 0; i < D; ++i) {
        scanf("%d", &T[i]);
    }
    for (j = 0; j < N; ++j) {
        scanf("%d%d%d", &A[j], &B[j], &C[j]);
    }
    
    for (i = 0; i < D; ++i) for (j = 0; j < N; ++j) {
        suit[i][j] = (A[j] <= T[i] && T[i] <= B[j]);
    }
    
    for (i = 0; i < D; ++i) for (j = 0; j < N; ++j) {
        //	-1 : impossible
        dp[i][j] = -1;
    }
    for (j = 0; j < N; ++j) if (suit[0][j]) {
        dp[0][j] = 0;
    }
    for (i = 0; i < D - 1; ++i) for (j = 0; j < N; ++j) if (dp[i][j] >= 0) {
        for (k = 0; k < N; ++k) if (suit[i + 1][k]) {
            if (dp[i + 1][k] < dp[i][j] + abs(C[j] - C[k])) {
                dp[i + 1][k] = dp[i][j] + abs(C[j] - C[k]);
            }
        }
    }
    
    int ans = -1;
    for (j = 0; j < N; ++j) {
        if (ans < dp[D - 1][j]) {
            ans = dp[D - 1][j];
        }
    }
    printf("%d\n", ans);
    
    return 0;
}

Measured memory_bytes: 2832
/*
If you want to shine like a sun, first burn like a sun.
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;
using namespace std;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ll long long int
#define ld long double
#define vi vector<int>
#define vl vector<ll>
#define v2i vector<vector<int>>
#define v2l vector<vector<ll>>
#define ppi pair<int,int>
#define ppl pair<ll,ll>
#define vpi vector<ppi>
#define vpl vector<ppl>
#define all(x) x.begin(),x.end()
#define ii int,int 
#define ff first    
#define ss second
#define forn(i,a,b) for(int i=a;i<b;i++)
#define forr(i,a,b) for(int i=a;i>=b;i--)
#define forv(i,m) for(auto i : m)
#define imx INT_MAX
#define imn INT_MIN
#define inf 9000000000000000000
#define minf -inf
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sze size()
#define rvs reverse 
#define itr iterator 
#define pre cout<<fixed<<setprecision(10);
#define umap unordered_map
#define uset unordered_set
#define pi 3.141592653589793
#define MAXN 100005
#define test1(x) cout << #x " = " << x << endl;
#define test2(x,y) cout << #x " = " << x << " " << #y " = " << y << endl;
const ll infinity = 9e18;


#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define MODM(a,b,md) ((a%md)*(b%md))%md
#define MODA(a,b,md) ((a%md)+(b%md))%md
#define ull unsigned long long int



bool compare(int a,int b) {return a > b;}
bool compare1(ppi a,ppi b) {return a.ff > b.ff;}
bool compare2(ppi a,ppi b) {return a.ss < b.ss;}
ll Npower(ll a,ll b) {ll product = 1; while(b){if(b&1){product = product*a;}a = a*a;b = b>>1;} return product;}
ll power(ll a,ll b,ll md) {ll product = 1; while(b){if(b&1){product = MODM(product,a,md);}a = MODM(a,a,md);b = b>>1;} return product%md;}
bool isprime(ll n){if(n < 2) return 0; ll i = 2; while(i*i <= n){if(n%i == 0) return 0; i++;} return 1;}
ll GCD(ll a,ll b) {return b==0 ? a:GCD(b,a%b);}
ll LCM(ll a,ll b) {return (a/GCD(a,b))*b; }


ll fact[MAXN],inv[MAXN];

void factorial()
{
    fact[0] = inv[0] = 1;

    for(ll i = 1; i < MAXN; i++)
    {
        fact[i] = (i*(fact[i-1]))%mod;
    }

    for(ll i = 1; i < MAXN; i++)
    {
        inv[i] = power(fact[i],mod-2,mod);
    }
}

int main()
{
    factorial();
    fast

/*
    #ifndef ONLINE_JUDGE
        freopen("input.txt",  "r",  stdin);
        freopen("output.txt", "w", stdout);
    #endif
//*/

        
    ll n,k;
    cin>>n>>k;

    vl v(n+1,0);

    v[0] = -inf;
    forn(i,1,n+1)
    {
        cin>>v[i];
    }    
     
    sort(all(v));    

    v[0] = 0;

    forn(i,1,n+1)
    {
        v[i] += v[i-1];
    }

    ll total = 0;

    forn(i,k,n+1)
    {
        ll x = (((fact[i-2]*inv[k-2])%mod)*inv[i-k])%mod; 
        total = ((((v[n]-(v[n-i+1]+v[i-1]))%mod)*x)%mod + total)%mod;    
    }

    cout<<total;





    return 0;
}

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

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

	int n;cin >> n;
	int m;cin >> m;
	ll x;cin >> x;
	vector<ll> c = vector<ll>(n,0);
	vector<vector<ll>> a(n,vector<ll>(m,0));

	for(int i = 0; i < n; i++){
		cin >> c[i];
		for(int j = 0; j < m; j++){
			cin >> a[i][j];
		}
	}

	ll ans = 9999999;
	for(int i = 0; i < (2<<n); i++){
		bool flag = true;
		for(int j = 0; j < m; j++){
			ll asum = 0;
			for(int k = 0; k < n; k++){
				if(i>>k&1){
					asum += a[k][j];
				}
			}
			if(asum < x){
				flag = false;
				break;
			}
		}
		if(flag){
			ll csum = 0;
			for(int j = 0; j < n; j++){
				if(i>>j&1){
					csum += c[j];
				}
			}
			ans = min(csum,ans);
		}
	}

	if(ans != 9999999){
		cout << ans << endl;
	}else{
		cout << "-1" << endl;
	}

	return 0;
}


Measured memory_bytes: 3624
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
bool check(string ss)
{
    string back=ss;
    reverse(back.begin(),back.end());
    return (ss==back);
}
int main()
{
    string ss;
    cin>>ss;
    int n=(int)ss.length();
    int frs=1,fre=(n-1)/2;
    int ses=(n+3)/2,see=n;
    frs--; fre--; ses--; see--;
    bool ans=(check(ss)&&check(ss.substr(frs,fre-frs+1))&&check(ss.substr(ses,see-ses+1)));
    puts(ans?"Yes":"No");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N, K; 
	cin >> N >> K; 
	int A[200010] = {}; 
	for(int i = 0; i < N; i++) cin >> A[i]; 
	for(int i = 0; i < N-K; i++){
		if(A[i] < A[i + K]) cout << "Yes" << "\n"; 
		else cout << "No" << "\n"; 
	}
}

Measured memory_bytes: 4448
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,K;
    cin >> N >> K;
    ll A[200010];
    rep(i,0,N) cin >> A[i];
    sort(A, A+N);
    ll zero = 0;
    rep(i,0,N){
        if(A[i] == 0) zero++;
    }
    vector<ll> plus, minus;
    rep(i,0,N){
        if(A[i] > 0) plus.push_back(A[i]);
        else if(A[i] < 0) minus.push_back(A[i]);
    }
    ll zero_cnt = N*(N-1)/2 - (N-zero) * (N-zero-1) / 2;
    ll lv = -1e18+1, rv = 1e18+1;
    while(rv - lv > 1){
        ll mid = (rv + lv) / 2;
        bool ok = true;
        ll res = 0;
        ll res_tmp = 0;
        rep(i,0,plus.size()){
            ll v = plus[i];
            if(mid >= 0){
                ll lv1 = i, rv1 = plus.size();
                while(rv1 - lv1 > 1){
                    ll mid1 = (lv1 + rv1) / 2;
                    if(v * plus[mid1] <= mid){
                        lv1 = mid1;
                    }else{
                        rv1 = mid1;
                    }
                }
                res += lv1 - i;
            }
            ll lv1 = -1, rv1 = minus.size();
            while(rv1 - lv1 > 1){
                ll mid1 = (rv1 + lv1) / 2;
                if(v * minus[mid1] <= mid){
                    lv1 = mid1;
                }else{
                    rv1 = mid1;
                }
            }

            res_tmp += lv1+1;
        }
        reverse(plus.begin(), plus.end());
        reverse(minus.begin(), minus.end());
        rep(i,0,minus.size()){
            ll v = minus[i];
            if(mid >= 0){
                ll lv1 = i, rv1 = minus.size();
                while(rv1 - lv1 > 1){
                    ll mid1 = (lv1 + rv1) / 2;
                    if(v * minus[mid1] <= mid){
                        lv1 = mid1;
                    }else{
                        rv1 = mid1;
                    }
                }
                res += lv1 - i;
            }
            ll lv1 = -1, rv1 = plus.size();
            while(rv1 - lv1 > 1){
                ll mid1 = (rv1 + lv1) / 2;
                if(v * plus[mid1] <= mid){
                    lv1 = mid1;
                }else{
                    rv1 = mid1;
                }
            }
            res_tmp += rv1;
        }
        reverse(plus.begin(), plus.end());
        reverse(minus.begin(), minus.end());
        // if(mid == 6) print(res);
        // print(res);
        // if(mid == -7) print(res);

        res += res_tmp/2;
        if(mid >= 0) res += zero_cnt;
        // print(mid, res);



        if(res >= K){
            ok = true;
        }else{
            ok = false;
        }

        if(ok){
            rv = mid;
        }else{
            lv = mid;
        }
    }
    print(rv);

    

}

Measured memory_bytes: 4084
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#include<bits/stdc++.h>
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/detail/standard_policies.hpp>*/

#define sz(s) (int)(s.size())
#define all(s) s.begin(), s.end()
#define rep(a, b, c) for(int a = b; a <= c; ++a)
#define per(a, b, c) for(int a = b; a >= c; --a)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
//using namespace __gnu_pbds;

typedef unsigned long long ull;
typedef long long ll;
/*typedef tree<pair<int, int>, 
null_type, less<pair<int, int>>, 
rb_tree_tag, tree_order_statistics_node_update>
ordered_set;*/
//find_by_order() order_of_key()

const double eps = 1e-7;
const int mod = 1e9+7, MXN = 5e5+17;
const int dx[] = {-1,-1,-1,0,0,0,1,1,1}, dy[] = {-1,0,1,-1,0,1,-1,0,1};

template<typename T>inline bool updmin(T &a, const T &b) {return a > b ? a = b,1 : 0;}
template<typename T>inline bool updmax(T &a, const T &b) {return a < b ? a = b,1 : 0;}

int h, w, n;
map<int, map<int, bool>>was;
map<int, map<int, bool>>used;
int X[MXN], Y[MXN], cnt[15];

int32_t main() { _
#ifdef DanQQQQQ
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	cin >> h >> w >> n;
	rep(i,1,n) {
		cin >> X[i] >> Y[i];
		was[X[i]][Y[i]] = 1;
	}
	rep(i,1,n)
		rep(cx,X[i]-1,X[i]+1)
			rep(cy,Y[i]-1,Y[i]+1) {
				if(cx-1 < 1 || cx+1 > h) continue;
				if(cy-1 < 1 || cy+1 > w) continue;
				if(used[cx][cy]) continue;
				int res = 0;
				rep(j,0,8)
					res += was[cx+dx[j]][cy+dy[j]];
				used[cx][cy] = 1;
				++cnt[res];
			}
	int sum = 0;
	rep(i,0,9) sum += cnt[i];
	cout << (h-2)*1ll*(w-2)-sum << endl;
	rep(i,1,9) cout << cnt[i] << endl;
	return 0;
}


Measured memory_bytes: 235392
p = input().split()
n = int(p[0])
m = int(p[1])
k = []
for i in range(n):
    l = input().split()
    for j in range(int(l[0])):
        k.append(l[j+1])
c = 0
for i in range(m):
    s = 0
    for j in k:
        if (i+1) == int(j):
            s += 1
    if s == n:
        c += 1
print(c)

Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

void solve() {
  long x, t;
  cin >> x >> t;
  cout << max(0l, x-t) << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
import math

N = int(input())

prime = [0 for _ in range(47 + 1)]
lst = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

for i in range(2, N + 1):
	num = i
	# 素因数分解
	for p in lst:
		while True:
			if num % p == 0:
				num //= p
				prime[p] += 1
			else: break
			if num == 1: break
		

_75 = 0
_25 = 0
_15 = 0
_5 = 0
_3 = 0

for i in range(len(prime)):
	if prime[i] >= 2:
		_3 += 1
	if prime[i] >= 4:
		_5 += 1
	if prime[i] >= 14:
		_15 += 1
	if prime[i] >= 24:
		_25 += 1
	if prime[i] >= 74:
		_75 += 1
		
def comb(a, b):
	return math.factorial(a) / (math.factorial(b) * math.factorial(a - b))
		
ans = 0
ans += _75
ans += (_3 - 1) * _25 # かけられている数で1引いているのは、かける数で使っているものをかけられる数でも使う場合を除くため
ans += (_5 - 1) * _15
if _5 >= 2:
	ans += (_3 - 2) * comb(_5, 2)

print(int(ans))

Measured memory_bytes: 38512
#include <bits/stdc++.h>
using namespace std;
int n, k;
string st;
int main()
{
    cin >> n >> k;
    cin >> st;
    int i = 1, j = 0, c = 0;
    for (; i <= k && j < n; ++ i)
    {
        if ((st[j] == 'A') ^ c)
            if (st[j] == 'B') st[j] = 'A'; else st[j] = 'B';
        else
        {
            j ++;
            c ^= 1;
        }
    }
    if (j >= n)
    {
        if (n & 1)
        {
            if (((k - i) & 1) ^ c) cout << "B"; else cout << "A";
            for (int i = 1; i < n; i += 2) cout << "BA";
        }
        else
            for (int i = 0; i < n; i += 2) cout << "BA";
        return 0;
    }
    for (int p = 0, g = j; p < n; ++ p, ++ g)
    {
        if (g < n) if ((st[g] == 'A') ^ c) cout << 'A'; else cout << 'B';
        else if (((g - n) & 1) ^ c) cout << 'A'; else cout << 'B';
    }
}


Measured memory_bytes: 772
a=list(input())
b=list(input())
c=list(input())
from collections import deque
a=deque(a)
b=deque(b)
c=deque(c)
if len(a)==0:
  print("A")
  exit(0)
t=a.popleft()
while True:
  if t=="a":
    if len(a)==0:
      print("A")
      exit(0)
    t=a.popleft()
  elif t=="b":
    if len(b)==0:
      print("B")
      exit(0)
    t=b.popleft()
  if t=="c":
    if len(c)==0:
      print("C")
      exit(0)
    t=c.popleft()


Measured memory_bytes: 3316
// Last Change: 03/21/2019 20:17:16.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

namespace NS {
void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}
} // namespace NS

int main() {
  ll A, B, C, D;
  cin >> A >> B >> C >> D;
  cout << min(A, B) + min(C, D) << endl;

  //NS::LoopUntilZeroInpput();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
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<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;


int main() {
    ll a,b;
    cin >> a >> b;
    if ((a<=8) && (b<=8)) cout << "Yay!" << endl;
    else cout << ":(" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
long long H, W;
template<typename T> inline bool chmax(T& a,T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T& a,T b) { if (a > b) { a = b; return true; } return false; }

long long div_A(){
    long long S = H * W;
    long long w = W / 3;
    long long A = H * w;
    long long B = H * ((W - w) / 2);
    long long C = S - A - B;
    long long res = max({A, B, C}) - min({A, B, C});
    if (W < 3) res = INF;
    return res;
}

long long div_B(){
    long long S = H * W;
    long long h = H / 3;
    long long A = h * W;
    long long B = W * ((H - h) / 2);
    long long C = S - A - B;
    long long res = max({A, B, C}) - min({A, B, C});
    if (H < 3) res = INF;
    return res;
}

long long div_C(){
    long long S = H * W;
    long long res = INF;
    long long h = H / 2;
    for (long long i = 1; i < W; i++) {
        long long A = h * i;
        long long B = H * (W - i);
        long long C = S - A - B;
        long long D = max({A, B, C}) - min({A, B, C});
        chmin(res, D);
    }
    return res;
}

long long div_D(){
    long long S = H * W;
    long long res = INF;
    long long w = W / 2;
    for (long long i = 0; i < H; i++) {
        long long A = w * i;
        long long B = W * (H - i);
        long long C = S - A - B;
        long long D = max({A, B, C}) - min({A, B, C});
        chmin(res, D);
    }
    return res;
}


int main(){
    cin >> H >> W;
    long long a = div_A(), b = div_B(), c = div_C(), d = div_D();
    long long ans = min({a, b, c, d});
    cout << ans << endl;
    return 0;
}

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

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int main(){
	ios::sync_with_stdio(false);
	int a,b;
	cin>>a>>b;
	if(a<=5)cout<<0<<endl;
	else if(a<=12)cout<<b/2<<endl;
	else cout<<b<<endl;	
	return 0;
}

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

int main(){

	int n, len;
	int cnt[4] = {0};
	string str;
	vector<char> vc;
/*
	while(scanf("%d, %s", &n, str) != EOF){
		for(int i=0; i<4; i++){
			if(str == blood[i]){
				cnt[i]++;
				break;
			}
			str = "";
		}
	}
	
	for(int i=0; i<4; i++){
		cout << cnt[i] << endl;
	}
*/

	while(getline(cin, str)){
		int valid = 0;
		len = str.length();
		for(int i=0; i<len; i++){
			if(str[i] == ','){
				valid = 1;
			}
			else if(valid == 1){
				if(str[i+1] == 'B') cnt[2]++;
				else if(str[i] == 'A') cnt[0]++;
				else if(str[i] == 'B') cnt[1]++;
				else cnt[3]++;
				break;
			}
		}
		str = "";
	}
	
	for(int i=0; i<4; i++){
		cout << cnt[i] << endl;
	}

	return 0;
	
}

Measured memory_bytes: 1172
N, M, X, Y = map(int,input().split())
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]

x.sort(reverse=True)
y.sort()

Z = y[0]
ans = "War"
if X < Z <= Y:
    if x[0] < Z:
        ans = "No War"

print(ans)

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

unsigned long long sub(string nStr, int nR, int nS, int nP);

int main()
{
    int N, K;
    cin >> N >> K;
    int R, S, P;
    cin >> R >> S >> P;
    string T;
    cin >> T;

    vector<string> sub_T(K, "");

    // sub問題用に文字列を分割する
    for(int i=0; i<N; i++)
    {
        sub_T[i%K] += T.at(i);
    }

    unsigned long long point = 0;
    for(auto i=sub_T.begin(); i!=sub_T.end(); i++)
    {
        point += sub(*i, R, S, P);
    }

    cout << point << endl;
    return 0;
}

// 戻り値 = 得点
unsigned long long sub(string nStr, int nR, int nS, int nP)
{
    unsigned long long res = 0;

    // sub問題
    // 連続して同じ手を出せない中で得点を最大にする

    char before = '-';

    for(auto it=nStr.begin(); it!=nStr.end(); it++)
    {
        // 前回と違う手なら勝てる
        if(*it != before)
        {
            switch(*it)
            {
                case 'r':
                    res += nP;
                    break;

                case 's':
                    res += nR;
                    break;

                case 'p':
                    res += nS;
                    break;
            }
          before = *it;
        }
        // 前回と同じ手なら次は勝てる
        else
        {
            before = '-';
        }
    }
    return res;
}

Measured memory_bytes: 5120
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

typedef pair<int,int> pii;
typedef unsigned int uint;
#define ff first
#define ss second

#define MAXN 3005

int arr[MAXN][MAXN];


int main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cerr.tie(NULL);

    string s,t;cin>>s>>t;

    for(uint i=1;i<=s.size();i++){
        for(uint j=1;j<=t.size();j++){

            if(s[i-1]==t[j-1]){
            
                arr[i][j]=max(arr[i-1][j-1]+1,max(arr[i][j-1],arr[i-1][j]));       
            
            }
            else
                arr[i][j]=max(arr[i][j-1],arr[i-1][j]);
    
        }

    }
#ifdef NOTINAIR
    cerr<<arr[s.size()][t.size()]<<endl;
#endif


    int i=s.size(),j=t.size();
    vector<char> ans;
    while(i&&j){

        if(arr[i-1][j-1]<arr[i][j] && arr[i][j]!=arr[i][j-1] && arr[i][j]!=arr[i-1][j]){
            assert(s[i-1]==t[j-1]);
            ans.push_back(s[i-1]);cerr<<"i: "<<i<<endl;
            i--;j--;
        }
        else{

            if(arr[i-1][j]>arr[i][j-1]) i--;
            else j--;   

        }
    }

    for(auto it = ans.rbegin();it!=ans.rend();it++){

        cout<<*it;

    }

    cout<<endl;
#ifdef NOTINAIR

    for(uint k=0;k<=s.size();k++){
        for(uint l=0;l<=t.size();l++)
            cerr<<arr[k][l]<<'\t';
        cerr<<endl;    
    }
#endif

    return 0;

}




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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const double EPS = 1e-10;

int main() {
    lint N, V;
    cin >> N >> V;
    vector<lint> A(N), B(N), C(N), D(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];
    rep(i, N) cin >> C[i];
    rep(i, N) cin >> D[i];

    vector<lint> E(0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            E.push_back(A[i] + B[j]);
        }
    }

    map<lint, lint> mp;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            mp[C[i] + D[j]]++;
        }
    }

    // dump(E);

    lint ans = 0;
    for (int i = 0; i < E.size(); i++) {
        lint F = V - E[i];
        ans += mp[F];
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 135788
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;
int ss[55];
int main()
{
    int n, m;
    memset(ss, 0, sizeof(ss));
    int a, b;
    cin >> n >> m;
    while(m--)
    {
        scanf("%d%d",&a,&b);
        ss[a]++;
        ss[b]++;
    }
    for(int i = 1; i <= n; ++i)
        cout << ss[i] << endl;
    return 0;
}


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

int n,m,q,ans;
vector<int> a,b,c,d;

void dfs(vector<int> v){
    if((int)v.size()==n+1){
        int sum=0;
        for(int i=0;i<q;i++){
            if(v[b[i]]-v[a[i]]==c[i]) sum+=d[i];
        }
        ans=max(ans,sum);
        return;
    }
    v.push_back(v.back());
    while(v.back()<=m){
        dfs(v);
        v.back()++;
    }
}

int main(){
    cin>>n>>m>>q;
    a=b=c=d=vector<int>(q);
    for(int i=0;i<q;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
    dfs(vector<int>(1,1));
    cout<<ans<<endl;
}

Measured memory_bytes: 3644
n = int(input())
for i in range(1, n + 1):
    x = i
    if x % 3 == 0:
        print(" ", i, sep="", end="")
    else:
        while x > 0:
            if x % 10 == 3:
                print(" ", i, sep="", end="")
                break
            x //= 10
print()

Measured memory_bytes: 8176
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<ll, ll, ll> T;

int N, K;
map<int, int> mp;

int main(void){
    
    scanf("%d %d", &N, &K);
    for(int i = 0; i < N; ++i){
        int a; scanf("%d", &a);
        ++mp[a];
    }
    
    vector<P> v;
    for(auto m : mp) v.push_back(make_pair(m.second, m.first));
    sort(v.begin(), v.end(), greater<P>());
    
    int cnt = 0;
    for(int i = 0; i < K && i < v.size(); ++i) cnt += v[i].first;
    if(N - cnt <= 0) printf("0\n");
    else printf("%d\n", N - cnt);
    
    return 0;
}



Measured memory_bytes: 11768
using System;

class Program
{
	public static void Main(string[] args)
	{
		// スペース区切りの整数の入力
        string[] input = Console.ReadLine().Split(' ');
        int a = int.Parse(input[0]);
        int b = int.Parse(input[1]);

		if(a+b == 15){
			Console.WriteLine("+");
		}
		else if(a*b == 15){
			Console.WriteLine("*");
		}
		else {
			Console.WriteLine("x");
		}
	}
}


Measured memory_bytes: 13140
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	class Edge{
		int to;
		int cost;
		Edge(int to, int cost){
			this.to=to;
			this.cost=cost;
		}
	}
	ArrayList<ArrayList<Edge>> g = new ArrayList<>();
	boolean used[];
	int x[];
	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();

		used = new boolean[n];
		x = new int[n];
		for(int i=0; i<n; i++) {
			g.add(new ArrayList<>());
		}
		for(int i=0; i<m; i++) {
			int s = sc.nextInt();
			int t = sc.nextInt();
			s--;t--;
			int c = sc.nextInt();
			g.get(s).add(new Edge(t, c));
			g.get(t).add(new Edge(s, -c));
		}

		for(int i=0; i<n; i++) {
			if(!used[i]) {
				dfs(i,0);
			}
		}

		for(int u=0; u<n; u++) {
			for(Edge e : g.get(u)) {
				if(x[e.to] != x[u]+e.cost) {
					System.out.println("No");
					sc.close();
					return;
				}
			}
		}
		System.out.println("Yes");
		sc.close();
	}

	public void dfs(int u, int dist) {
		x[u]=dist;
		used[u]=true;
		for(Edge e : g.get(u)) {
			if(!used[e.to]) {
				dfs(e.to, dist+e.cost);
			}
		}
	}
}


Measured memory_bytes: 89588
#include <stdio.h>

int main(void){
	
	int a,b,d,r;
	
	double f;
	
	scanf("%d %d",&a,&b);
	
	d = a/b;
	r = a%b;
	f = (double)a/(double)b;
	
	printf("%d %d %lf\n",d,r,f);
	
	return 0;
	
};

Measured memory_bytes: 636
#include <iostream>
#include<bits/stdc++.h>
#define MAX 100005
using namespace std;

int dp[MAX][2];

bool playgame(int currentplayer,int n,int k,int steps[])
{
 
  if(dp[k][currentplayer]!=-1 )  
  {
      return  (dp[k][currentplayer]==0? false:true);
  }
    
    
  int nextplayer = (currentplayer==0 ? 1 : 0);
  
  for(int i=0;i<n;i++)
  {
      if(k-steps[i]>=0)
      {
          bool cannextplayerwin=playgame(nextplayer,n,k-steps[i],steps);
          
          if(cannextplayerwin==false)
          
          {
              dp[k][currentplayer]=true;
              return true;
          }
          
      }
     
  }
  dp[k][currentplayer]=0;
  return false;
  
    
}


void findit(int n,int k,int steps[])
{
    //1 denotes Taro
    //2 denotes Jiro
    
    //map<pair<int,int>,int> v;
    
    for(int i=0;i<=MAX;i++)
    {
        for(int j=0;j<2;j++)
        {
         dp[i][j]=-1;   
        }
    }
    int answer=playgame(0,n,k,steps);
    
    if(answer)
    {
        cout<<"First";
    }
    
    else cout<<"Second";
    
  
}


int main()
{

    int n;
    cin>>n;
    
    int k;
    cin>>k;
    
    int steps[n];
    
    for(int i=0;i<n;i++)
    {
        cin>>steps[i];
    }
    
    findit(n,k,steps);

	return 0;
}


Measured memory_bytes: 8832