akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define INF 1LL << 60;
#define LLINF 1e12
#define PI 3.14159265359
#define ALL(a) (a).begin(), (a).end()
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
int dy8[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dx8[] = {0, 1, 0, -1, 1, 1, -1, -1};
int ny, nx;
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

ll llpow(ll x, ll y)
{
    ll ans = 1;
    REP(i, y)
    ans *= x;
    return ans;
}

ll llmin(ll x, ll y) { return x < y ? x : y; }
ll llmax(ll x, ll y) { return x > y ? x : y; }

unsigned GetDigit(unsigned num) { return to_string(num).length(); }

template <typename Container>
bool exist_in(const Container &c, const typename Container::value_type &v)
{
    return (c.end() != std::find(c.begin(), c.end(), v));
}

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

ll nCr(int n, int r)
{
    if (n == r or n == 0)
        return 1;
    if (n < r)
        return 0;
    if (r == 1)
        return n;
    return nCr(n - 1, r - 1) + nCr(n - 1, r);
}

//素因数分解
vector<ll> decom;

void decompositPrime(ll n)
{
    ll a = 2;
    while (n >= a * a)
    {
        if (n % a == 0)
        {
            decom.push_back(a);
            n /= a;
        }
        else
        {
            a++;
        }
    }
    decom.push_back(n);
}

//std::cout << std::defaultfloat << std::setprecision(10);
////////////////////////////////////////
int main()
{
    int N; cin >> N;
    string S; cin >> S;

    int Wcnt=0, Rcnt=0;

    REP(i,N){
        if(S[i]=='R') Rcnt++;
    }

    int ans = max(Wcnt, Rcnt);
    REP(i,N){
        if(S[i]=='R') Rcnt--; 
        else Wcnt++;
        int now = max(Rcnt, Wcnt);
        ans = min(ans, now);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3712
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

int H, W, K;
string S[300];
int sum[301][301] ={};
int a[300][300];

int calc(int y1, int x1, int y2, int x2){
    return sum[y2][x2] - sum[y2][x1] - sum[y1][x2] + sum[y1][x1];
}

int c = 1;
void solve(int y1, int x1, int y2, int x2){
    if(calc(y1, x1, y2, x2) == 1){
        for(int i=y1; i<y2; i++){
            for(int j=x1; j<x2; j++){
                a[i][j] = c;
            }
        }
        c++;
        return;
    }
    for(int i=y1+1; i<y2; i++){
        if(calc(y1, x1, i, x2) > 0 && calc(i, x1, y2, x2) > 0){
            solve(y1, x1, i, x2);
            solve(i, x1, y2, x2);
            return;
        }
    }
    for(int i=x1+1; i<x2; i++){
        if(calc(y1, x1, y2, i) > 0 && calc(y1, i, y2, x2) > 0){
            solve(y1, x1, y2, i);
            solve(y1, i, y2, x2);
            return;
        }
    }

}

signed main(){
    cin >> H >> W >> K;
    rep(i, H){
        cin >> S[i];
        rep(j, W){
            sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j];
            if(S[i][j] == '#') sum[i+1][j+1]++;
        }
    }

    solve(0, 0, H, W);
    rep(i, H){
        rep(j, W){
            if(j != 0) cout << " ";
            cout << a[i][j];
        }
        cout << endl;
    }
}

Measured memory_bytes: 4512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    int n;cin>>n;
    string s[n];rep(i,n)cin>>s[i];
    map<string,bool> flag;
    string before = s[0];
    flag[before]=true;
    rep1(i,n-1){
        if(flag[s[i]]){co("No");return 0;}
        if(before[before.size()-1]!=s[i][0]){co("No");return 0;}
        flag[s[i]]=true;
        before = s[i];
    }
    co("Yes");
}

Measured memory_bytes: 256
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()

Measured memory_bytes: 95800
#include<bits/stdc++.h>
using namespace std;
vector<int>T[200001];
int A[200001];
void dfs(int x,int la) {
	A[x]+=A[la];
	for(int i=0; i<T[x].size(); ++i) {
		int y=T[x][i];
		if(y==la)continue;
		dfs(y,x);
	}
}
int main() {
	int a,b,x,y;
	cin>>a>>b;
	for(int i=1; i<a; i++)scanf("%d%d",&x,&y),T[x].push_back(y),T[y].push_back(x);
	for(int i=1; i<=b; i++)scanf("%d%d",&x,&y),A[x]+=y;
	dfs(1,0);
	for(int i=1; i<=a; i++)printf("%d ",A[i]);
}

Measured memory_bytes: 23424
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N, K;
  cin >> N >> K;
  vector<int> data(N);
  for (int i = 0; i < N; i++) {
    cin >> data.at(i);
  }
  sort(data.begin(),data.end());
  reverse(data.begin(),data.end());
  int ans = 0;
  for (int i = 0; i < K; i++) {
    ans += data.at(i);
  }
  cout << ans << endl;
  return 0;
}

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

#define t_case ll test;cin>>test;while(test--)
#define left(nod) 2*nod
#define right(nod) 2*nod+1
#define ss second
#define ff first
#define pb push_back
#define pll pair<ll,ll>
#define FAST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define deb(a) cout<<#a<<": "<<a;cout<<endl;
#define deba(a...) cout<<endl;cout<<#a<<": ";for(auto it:a)cout<<it<<" ";cout<<endl;
ll par[200009];
ll find(ll a)
{
	if(par[a]==a)return a;
	
	return par[a]=find(par[a]);
	
}

void dsu(ll a,ll b)
{
	a=find(a);b=find(b);
	
	if(a>b)swap(a,b);
	
	par[b]=a;
	
}


int main()
{
	FAST;//not faster than scanf printf
	
	ll n,m;cin>>n>>m;
	
	for(ll i=1;i<=n;i++)par[i]=i;
	
	for(ll i=1;i<=m;i++)
	{
		ll a,b;cin>>a>>b;
		dsu(a,b);
	}
	vector <ll> freq(n+9,0);
	for(ll i=1;i<=n;i++){par[i]=find(i);freq[par[i]]++;}
	ll maxi=0;
	
	for(ll i=1;i<=n;i++)maxi=max(maxi,freq[i]);
	
	cout<<maxi;
	
	
	
	
	
}


Measured memory_bytes: 6356
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<functional>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<string.h>
#include<limits.h>
using namespace std;

signed main() {
	vector<int>x, y;
	int a; cin >> a;
	for (int b = 0; b < a; b++) {
		for (int c = b + 1; c < a; c++) {
			string d="? ";
			for (int e = 0; e < a; e++) {
				if (b == e || c == e) {
					d += '1';
				}
				else {
					d += '0';
				}
			}
			cout << d << endl;
			int n; cin >> n;
			if (n) {
				x.push_back(b); y.push_back(c);
			}
		}
	}
	cout << "!";
	for (int i = 0; i < x.size(); i++) {
		cout << ' ';
		cout << '(' << x[i] << ',' << y[i] << ')';
	}
	cout << endl;
}

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define pii pair<int,int>
#define ll long long
#define el '\n'

using namespace std;

int n,m;
int cost[10]={0,2,5,5,4,5,6,3,7,6};
vector <pii> v; // (cost,digit)
vector <int> ans;
vector <pii> dp[2005];

bool cmp(pii a, pii b){
    if (a.fi!=b.fi) return (a.fi<b.fi);
    
    return (a.se>=b.se);
}

int kpk(int a,int b){
    int tm=a,fpb=b;

    while (tm%fpb!=0){
        int c=fpb;
        fpb=tm%fpb;
        tm=c;
    }

    return (a*b)/fpb;
}

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

    cin >> n >> m;
    for (int i=0;i<m;i++){
        int tm;
        cin >> tm;
        v.pb(mp(cost[tm],tm));
    }

    sort(v.begin(),v.end(),cmp);
    int lcm=v[0].fi;
    for (auto x : v){
        lcm=kpk(lcm,x.fi);
    }
     
    int exact=n/lcm;
    if (exact>0){
        exact--;
        n-=lcm*exact;
    }
    
    for (int i=0;i<exact*(lcm/v[0].fi);i++){
        ans.pb(v[0].se);
    }

    vector <pii> rek;
    bool cek[10];
    for (int i=0;i<10;i++) cek[i]=0;
    for (auto x : v){
        if (cek[x.fi]) continue;
        if (x.fi==4 && cek[2]) continue;
        if (x.fi==6 && (cek[3] || cek[2])) continue;

        cek[x.fi]=1;
        rek.pb(x); 
    }

    

        priority_queue <int,vector<int>,greater<int>> pq;
        pq.push(0);

        while (!pq.empty()){
        //    cerr << pq.top() << " " << dp[pq.top()].size() << el;
            int id=pq.top();
            pq.pop();
            for (auto x : rek){
                if (id+x.fi>n) break;
                int a=dp[id].size()+1,b=dp[id+x.fi].size();
                if (b==0) pq.push(id+x.fi);
                if (a>b){
                    for (int i=0;i<a-1;i++){
                        if (i<b){
                            dp[id+x.fi][i]=dp[id][i];
                        }else dp[id+x.fi].pb(dp[id][i]);
                    }
                    dp[id+x.fi].pb(mp(x.se,x.fi));
                    sort(dp[id+x.fi].begin(),dp[id+x.fi].end(),greater<pii>());
                } else if (a==b){
                    vector <pii> tm;
                    for (auto z : dp[id]) tm.pb(z);
                    tm.pb(mp(x.se,x.fi));
                    sort(tm.begin(),tm.end(),greater<pii>());
                    bool tuker=0;
                    for (int i=0;i<a;i++){
                        if (tm[i]>dp[id+x.fi][i]){
                            tuker=1;break;
                        } else if (tm[i]<dp[id+x.fi][i]) break;
                    }
                    if (tuker){
                        for (int i=0;i<a;i++){
                            dp[id+x.fi][i]=tm[i];
                        }
                    }
                }
            }

        }

        for (auto x : dp[n]) ans.pb(x.fi);
    

    sort(ans.begin(),ans.end(),greater<int>());
    for (auto x : ans) cout << x;
    cout << el;

    return 0;
}

Measured memory_bytes: 2048
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in range(1,26,2):
  for j in range(26):
   if''.join(e(c,i,j)for c in'that')in s or''.join(e(c,i,j)for c in'this')in s:return(i,j)
for _ in[0]*int(input()):
 s=input()
 a=''.join(e(c,*f())for c in z)
 t=str.maketrans(a,z)
 print(s.translate(t))


Measured memory_bytes: 5600
// God put a smile upon your face <3

#include <bits/stdc++.h>

#define slld(longvalue) scanf("%lld", &longvalue)

#define ll long long
#define ull unsigned long long
#define pll pair < long long, long long >

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

#define pb push_back

#define bug printf("BUG\n")

#define mxlld LLONG_MAX
#define mnlld -LLONG_MAX

#define mxd 2e8
#define mnd -2e8

#define pi 3.14159265359

using namespace std;

bool check(ll n, ll pos)
{
	return n & (1LL << pos);
}

ll Set(ll n, ll pos)
{
	return n = n | (1LL << pos);
}

ll arr[200005];

int main()
{
    ll i, j, k, l, m, n, o, r, q;
    ll testcase;
    ll input, flag, tag, ans;

//    freopen("input.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

    while(cin >> n)
    {
		ll ans = 0;

		for(ll i = 1; i <= n; i++) cin >> arr[i];

		for(ll i = 2; i <= n; i++)
		{
			ans += max(0LL, arr[i - 1] - arr[i]);
			arr[i] = max(arr[i], arr[i - 1]);
		}

		cout << ans << endl;
    }



}





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

using ll = long long;

// Segment-Tree
struct SegmentTree {
  int n;
  vector<ll> dat;
  
  // Constructor
  SegmentTree(int _n) {
    init(_n);
  }
  
  // 初期化
  void init(int _n) {
    n = 1;
    while (n < _n) n *= 2;
    dat.resize(2 * n - 1, 0);
  }
  
  // i番目の値をxに変更
  void update(int i, ll x) {
    i += n - 1; // 葉のノード
    dat[i] = x;
    while (i > 0) { // 更新
      i = (i - 1) / 2;
      dat[i] = max(dat[2 * i + 1], dat[2 * i + 2]);
    }
  }
  
  // [a, b)の最小値
  // k:ノードの番号 [l, r)がkに対応づいている
  // query(a, b, 0, 0, n)と呼ぶ
  ll query(int a, int b, int k = 0, int l = 0, int r = -1) {
    if (r == -1) r = n;
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return dat[k];
    else {
      ll vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
      ll vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
      return max(vl, vr);
    }
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  vector<int> h(n);
  for (int i = 0; i < n; i++) cin >> h.at(i);
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++) cin >> a.at(i);
  
  SegmentTree seg(n);
  
  vector<ll> dp(n);
  for (int i = 0; i < n; i++) {
    dp.at(i) = seg.query(0, h.at(i), 0, 0) + a.at(i);
    seg.update(h.at(i) - 1, dp.at(i));
  }
  
  cout << seg.query(0, n, 0, 0) << '\n';
}

Measured memory_bytes: 8320
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Mid ((l+r)/2)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout);
const int maxn=2e5+5,mod=1e9+7,inf=0x3f3f3f3f;
int n,m,Q,K,T;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}int fa[maxn],siz[maxn];
int sum[maxn];
int find(int x){return (fa[x]==x)?x:fa[x]=find(fa[x]);}
signed main(){
    //file(a);
    n=read();m=read();
    rep(i,1,n)fa[i]=i,siz[i]=1;
    rep(i,1,m){
        int x=read(),y=read();
        int fx=find(x),fy=find(y);
        if(fx==fy)continue;
        if(siz[fx]>siz[fy])swap(fx,fy);
        fa[fx]=fy;siz[fy]+=siz[fx];
    }int ans=0;
    rep(i,1,n)sum[find(fa[i])]++;
    rep(i,1,n)ans=max(ans,sum[i]);
    printf("%d\n",ans);



    return 0;
}


Measured memory_bytes: 6084
#include<stdio.h>
int main()
{
    int i;
    int n, a;
    int ans = 0;
    scanf("%d", &n);
    i = 0;
    while(1){
        scanf("%d", &a);
        if(a != i + 1){
            ans++;
        }else{
            i++;
        }
        if(i + ans == n) break;
    }
    if(ans == n) ans = -1;
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>

#define INF (1<<29)
 
using namespace std;
 
int main(void){
  
  int n,m,p,a,b,x,y,z,in;
  double dp[(1<<8)][31],graph[31][31];
  vector<int>t;
  
  while(cin >> n >> m >> p >> a >> b){
    if(!(n|m|p|a|b))break;
    
    t.clear();
    
    fill(graph[0],graph[31],-1);
    fill(dp[0],dp[(1<<8)],INF);

    for(int i=0;i<n;i++){
      cin >> in;
      t.push_back(in);
    }
    
    for(int i=0;i<p;i++){
      cin >> x >> y >> z;
      graph[x][y]=graph[y][x]=z;
    }
    
    dp[0][a]=0;
    double res=INF;
    for(int S=0;S<(1<<8);S++){
      res=min(res,dp[S][b]);
      for(int v=1;v<=m;v++){
	for(int i=0;i<n;i++){
	  if(!(S>>i & 1)){
	    for(int u=1;u<=m;u++){
	      if(graph[v][u]>=0){
		dp[S|(1<<i)][u]=min(dp[S|(1<<i)][u],dp[S][v]+graph[v][u]/t[i]);
	      }
	    }
	  }
	}
      }
    }
    if(res==INF)printf("Impossible\n");
    else printf("%.3f\n",res);
  }
  
  return 0;
}

Measured memory_bytes: 1312
<?php
fscanf(STDIN, '%d', $N);

$d = $N % 100 % 10;

switch ($d) {
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
        echo 'hon';
        break;
    case 0:
    case 1:
    case 6:
    case 8:
        echo 'pon';
        break;
    default:
        echo 'bon';
        break;
}

echo PHP_EOL;


Measured memory_bytes: 16004
#include <bits/stdc++.h>
using std::cerr;
using std::endl;

const int N = 3005;
int n, P, ans, C[N][N], S[N][N];

inline int fpow(int x, int y, int mod) {
  int ret = 1;
  for ( ; y; y >>= 1, x = 1ll * x * x % mod)
    if (y & 1) ret = 1ll * ret * x % mod;
  return ret;
}

int main() {
  std::cin >> n >> P;
  S[0][0] = C[0][0] = 1;
  for (int i = 1; i < N; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
      S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j]) % P;
    }
  }
  for (int i = 0; i <= n; ++i) {
    int sum = 0, pow = fpow(2, n - i, P);
    for (int j = 0, val = 1; j <= i; ++j) {
      sum = (sum + 1ll * S[i + 1][j + 1] * val) % P;
      val = 1ll * val * pow % P;
    }
    sum = 1ll * sum * fpow(2, fpow(2, n - i, P - 1), P) % P
      * C[n][i] % P * (i & 1 ? P - 1 : 1) % P;
    ans = (ans + sum) % P;
  }
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 58892
import re
  
# 正解法   S=?b?? T=ab -> ans:abaa
def solve(s, t):
    s = s.replace('?', '.')
    ls, lt = len(s), len(t)
    if ls < lt:
        return 'UNRESTORABLE'
    ans = []
    for i in range(ls - lt + 1):
        m = re.match(s[i:i + lt], t)
        if m is None:
            continue
        ans.append((s[:i] + t + s[i + lt:]).replace('.', 'a'))
    if not ans:
        return 'UNRESTORABLE'
    return min(ans)
  
  
s = input().strip()
t = input().strip()
  
print(solve(s, t))

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e9
typedef long long ll;
using namespace std;
//�I�[�o�[�t���[�ɋC���‚���您����������
//�m�F�Y���Ȃ您����������

struct P{
    int h;
    int m;
};

int main() {
    vector<P> time;

    int n; cin >> n;
    rep(i,n) {
        int h1, m1; cin >> h1 >> m1;
        time.push_back({h1,m1});
    }

    int m; cin >> m;
    rep(i,m) {
        int h1, m1; cin >> h1 >> m1;
        time.push_back({h1,m1});
    }

    sort(ALL(time),[](P a, P b){
        if(a.h==b.h) return a.m < b.m;
        return a.h < b.h;
    });

    cout << time[0].h << ":";
    printf("%02d",time[0].m);

    REP(i,1,time.size()) {
        if(time[i].h!=time[i-1].h || time[i].m!=time[i-1].m) {
            cout << " " << time[i].h << ":";
            printf("%02d",time[i].m);
        }
    }
    cout << endl;


    


    return 0;
}


Measured memory_bytes: 3252
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

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

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

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

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


template <typename T>
T amarinasi(T a,T b){
    if(a%b==0)
{
    return a/b;
}
else if(a%b>0)
{
    return a/b+1;
}
else
{
    return a/b-1;
}
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

//----------------------------------------------------------------

int main(){
ll n;
cin>>n;
map<string,ll>rensou;
string s;

for(int i=0;i<n;i++){
cin>>s;
rensou[s]++;
}
ll m;
cin>>m;
for(int i=0;i<m;i++){
    cin>>s;
    rensou[s]--;
}
ll ans=0;
for(auto f:rensou){
    chmax(ans,f.second);
}
cout<<ans<<endl;
}












Measured memory_bytes: 256
from collections import defaultdict
d = defaultdict(lambda:defaultdict(list))

def cal(s,k):
    if k == 0:
        d[0][s].append(str(s))
    else:
        m = max(0,s-1)
        M = min(9,s+1)
        for i in range(m,M+1):
            for j in d[k-1][i]:
                d[k][s].append(str(s)+j)

for k in range(10):
    for s in range(10):
        cal(s,k)

ans = []
for k in range(10):
    for s in range(10):
        for i in d[k][s]:
            ans.append(int(i))

ans = list(set(ans))
ans.sort()
ans = ans[1:]
k = int(input())
print(ans[k-1])

Measured memory_bytes: 80220
import java.util.*;

import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		int N = Integer.parseInt(in.readLine());
		String[] tokens = in.readLine().split(" ");
		int[] d = new int[N];
		for (int i = 0; i < N; ++i) {
			d[i] = Integer.parseInt(tokens[i]);
		}
		int sum = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = i + 1; j < N; ++j) {
				sum += d[i] * d[j];
			}
		}
		System.out.println(sum);

	}
}


Measured memory_bytes: 22996
s = input()
s_list =  list(s)
jun = 0
ans = 1

while(len(s_list)):
    if jun % 2 == 0:
        if s_list[jun] == "L":
            ans = 0
    if jun % 2 == 1:
        if s_list[jun] == "R":
            ans = 0
    jun += 1
    if jun == len(s_list):
      break
if ans == 1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>

using namespace std;

int main()
{
    int n,max=-1;
    cin>>n;
    string temp;
    map<string, int> score;
    set<string> backup;
    for(int i = 0;i < n;i++)
    {
        cin>>temp;
        backup.insert(temp);
        score[temp]++;
        if(score[temp]>max)
            max=score[temp];
    }
    //printf("max is %d\n",max);
    for (auto value : backup) {
        //cout<<value<<endl;
        if(score[value]==max)
        {
            cout<<value<<endl;
        }
    }

    return 0;
}


Measured memory_bytes: 34560
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

using namespace std;

typedef long long ll;

typedef pair<int,int> Pi;
typedef pair<int,Pi> P2;
const ll inf=100000000000000;
struct edge{
	int to,cost;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

#define MAX_N 200002
int dp[26][MAX_N]={};
bool d[MAX_N]={};
int pa[MAX_N];
vector<edge> G[MAX_N];
Pi cost[MAX_N]={};
vector<int> child[MAX_N];
vector<int> ra[MAX_N];
priority_queue<P2,vector<P2>,greater<P2>> que;
Pi a[100005]={};
Pi b[100005]={};
int main() {
	int n;
	cin>>n;
	rep(i,100001)a[i].second=i;
	rep(i,100001)b[i].second=i;

	rep(i,n){
		int v;
		cin>>v;
		if(i%2==0){
			a[v].first++;
		}else{
			b[v].first++;
		}
	}
	sort(a,a+100001);
	sort(b,b+100001);
	if(a[100000].second!=b[100000].second){
		cout<<(n-a[100000].first-b[100000].first)<<endl;
	}else{
		cout<<(n-max(a[100000].first+b[99999].first,a[99999].first+b[100000].first))<<endl;

	}
	return 0;
}





Measured memory_bytes: 18688
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
#define mem(a, b) memset(a, b, sizeof(a))
#define REP(i, a) for (int i = 0; i < a; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(a) a.begin(), a.end()
 
inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(10);
}
 
inline void print_vector(vector<int> &A){
    for (auto&& x : A){
        cout << x << " ";
    }
    cout << endl;
}
 
inline void print_array(const int A[], int n) {
    REP(i, n) {
        if (i < n - 1) {
            cout << A[i] << " ";
        } else {
            cout << A[i] << endl;
        }
    }
}
 
inline void solve() {
    int n;
    cin >> n;
 
    cout << 1 - n << endl;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    quickread();
    int t = 1;
 
    for (int _ = 0; _ < t; _++) {
        solve();
    }
 
    return 0;
}

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

int main(){
    int n; cin >> n;
    string ans = "Yes";
    vector<char> s(n);
    rep(i,n) cin >> s.at(i);
    if(n % 2 == 1) ans = "No";
    for(int i = 0;i < n/2;i++){
        if(s.at(i) != s.at(i + (n/2))){
            ans = "No";
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;

int N, K;
vector<ll> H;

ll INF = 1145141919810893;

vector<ll> pressAr;

void press() {
	for (int i = 0; i < H.size(); i++) {
		pressAr.push_back(H[i]);
	}
	sort(pressAr.begin(), pressAr.end());
	pressAr.erase(unique(pressAr.begin(), pressAr.end()), pressAr.end());
	for (int i = 0; i < H.size(); i++) {
		H[i] = lower_bound(pressAr.begin(), pressAr.end(), H[i]) - pressAr.begin();
	}
}

ll dp[300 + 10][300 + 10][300 + 10];

int main() {
	cin >> N >> K;
	H.resize(N + 1);
	for (int i = 0; i < N; i++)cin >> H[i];
	//便宜上0も圧縮配列に入れる。もちろん0なので圧縮されても0番である。
	H[N] = 0;

	press();
	
	for (int i = 0; i <= N; i++)
		for (int j = 0; j <= K; j++)
			for (int k = 0; k <= pressAr.size(); k++)
				dp[i][j][k] = INF;
	dp[0][0][0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= K; j++) {
			for (int k = 0; k <= pressAr.size(); k++) {
				if (dp[i][j][k] == INF)continue;
				//塗り替えをする場合
				if (j + 1 <= K) {
					dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k]);
				}
				//塗り替えをしない場合
				if (H[i] <= k) {
					//今見てるのが今までより低いならば、高さを合わせてk -> H[i]に
					dp[i + 1][j][H[i]] = min(dp[i + 1][j][H[i]], dp[i][j][k]);
				}
				else {
					//今見てるのが今までより高いならば、高さをそこに合わせて、ぬるべき回数を増やす
					dp[i + 1][j][H[i]] = min(dp[i + 1][j][H[i]], 
						dp[i][j][k] + (pressAr[H[i]] - pressAr[k]));
				}
			}
		}
	}

	ll ans = INF;
	for (int j = 0; j <= K; j++) {
		for (int k = 0; k <= pressAr.size(); k++) {
			ans = min(ans, dp[N][j][k]);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 227584
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {

		String s = sc.next();
		int n = s.length() - 1;

		long ans = 0L;
		for (int i=0; i<Math.pow(2,n); i++) {

			//ビット全探索で文字列Sに"+"を挿入していく
			StringBuilder sb = new StringBuilder(s);
			for (int j=n-1; j>=0; j--) {
				if ((1&i>>j) == 1) {
					sb.insert(j+1,"+");
				}
			}

			//"+"入りの文字列をsplitして足し合わせる
			String[] ar = sb.toString().split("\\+",0);
			for (int j=0; j<ar.length; j++) {
				ans += Long.parseLong(ar[j]);
			}

		}

		System.out.println(ans);

	}
}

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

#define MAX 100000

int partition(int);
void swap(int, int);
void printa(int, int);

int *a;

int main(){
 
  int n, i, p;

  scanf("%d", &n);

  a = malloc(sizeof(int)*n+1);

  for(i = 0; i < n; i++)
    {
      scanf("%d", &a[i]);
    }
    
  p = partition(n);
  
  printa(p, n);
  
  return 0;
}

int partition(int n)
{
  int i, count=0;
  
  for( i = 0; i < n-1; i++)
  {
    if(a[i] <= a[n-1])
      {
	if(i >= count)
	  {
	    swap(i,count);
	    count++;
	  }
      }


  }
  if(a[count] > a[n-1])swap(count,n-1);
  else swap(++count,n-1);
  
    return count;
}
void swap(int i, int count)
{
  int temp;

  temp = a[i];
  a[i] = a[count];
  a[count] = temp;

  return;
}

void printa(int p, int n)
{
  int i;
  
for(i = 0; i < p; i++)
    {
      printf("%d ", a[i]);
    }

 printf("[%d] ", a[i]);
 i++;
 
  for(; i < n-1; i++)
    {
      printf("%d ", a[i]);
    }
  printf("%d", a[i]);
  printf("\n");
  

}



Measured memory_bytes: 2108
#include<stdio.h>
int main()
{
	int a,b;

	scanf("%d",&a);
	scanf("%d",&b);

	if(a==b){
		printf("a == b\n");
		}

	else if(a>b){
		printf("a > b\n");
		}

	else{	
		printf("a < b\n");
		}

	return 0;
}


Measured memory_bytes: 2080
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;
    int road = a+b-1;
    cout << a*b-road << endl;
    return 0;
}


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

ll sum(vector<ll>&a,ll l ,ll r)
{
  ll s=0;
  for(ll i=l;i<=r;i++)
    s+=a[i];
  return s;
}


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

  vector<ll>a(n);
  for(auto &it:a)
      cin>>it;
  ll dp[n+5][n+5];
 /* for(ll i=0;i<n;i++)
    for(ll j=0;j<n;j++)
      dp[i][j]=0;*/

  for(ll l=n-1;l>=0;l--)
  {
    for(ll r=l;r<n;r++)
    {
      if(l==r)
        dp[l][r]=0;
      else
      {
        ll s=sum(a,l,r);
        dp[l][r]=inf;
        for(ll i=l;i<r;i++)
        {
          dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]+s);
        }
      }
    }
  }

  cout<<dp[0][n-1]<<endl;



}



Measured memory_bytes: 4848
#include<stdio.h>
 
int n,a,i,l,r,ans;
 
int main(){
  scanf("%d",&n);
  while(n>0){
    n--;
     
    l=0;
    r=0;
    ans=0;
    for(i=0;i<10;i++){
      scanf("%d",&a);
      if(l<a)l=a;
      else if(r<a)r=a;
      else ans=1;
    }
 
    if(ans==0)printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}


Measured memory_bytes: 2040
main :: IO ()
main = do
    x <- read <$> getLine
    putStrLn $ show $ solve x

solve :: Int -> Int
solve x = maximum $ filter isExp [1..x]


isExp :: Int -> Bool
-- xがべき乗数か判定

isExp 1 = True
isExp x =
    not $ null $ filter judge [a | a <- [2..x], x `mod` a == 0]
    where judge = \m -> case isExpOf x m of
            Nothing -> False
            Just n  -> n > 1


isExpOf :: Int -> Int -> Maybe Int
-- aをbの累乗で表せるか判定
-- 表せなかったらNothing、表せたら指数を返す

isExpOf 1 _ = Just 0
isExpOf x m = 
    case (x `mod` m == 0) of
        False -> Nothing
        True  -> do
            n <- isExpOf (x `div` m) m
            return (n + 1)

Measured memory_bytes: 508
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for (int i = a; i < b; i++)
using namespace std;

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <bitset>

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

	vector<string> s(N);
	rep(i, N) {
		cin >> s.at(i);
	}

	int M;
	cin >> M;

	vector<string> t(M);
	rep(i, M) {
		cin >> t.at(i);
	}

	int ans = 0;

	rep(i, N) {
		int cntN = 0;
		rep(j, N) {
			if (s.at(i) == s.at(j)) {
				cntN++;
			}
		}			   	

		int cntM = 0;
		rep(j, M) {
			if (s.at(i) == t.at(j)) {
				cntM++;
			}
		}
		ans = max(ans, cntN - cntM);	
	}

	cout << ans << endl;
}


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

int main() {
  int n,cur=0,ans=0;
  cin >> n;
  char c;
  for(int i=0; i<n; i++){
    cin >> c;
    if(c=='I'){
      cur++;
      ans=max(ans,cur);
    }else{
      cur--;
    }
  }
  cout << ans << endl;
}

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

int main()
{
  int n;
  cin >> n;
  int sit[100010];
  for(int i = 0; i < n; i++ )
  {
    int a;
    cin >> a;
    sit[a-1] = i + 1;
  }
  
  for(int i = 0; i < n; i++ )
  {
    cout << sit[i] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1152
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
s = input()
ans = s.count('R')
if ans == 2 and s[1] != 'R':
    ans -= 1
print(ans)

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

x = list(map(int,input().split()))
x.sort()

con = 0

for p in range(n):
    for q in range(p+1,n):
        for r in range(q+1,n):
            if x[p] != x[q] and x[q] != x[r] and x[r] < (x[p] + x[q]) and x[q] < (x[p] + x[r]) and (x[r]-x[p]) < x[q] and (x[r]-x[q]) < x[p] and (x[q]-x[p]) < x[r]:
                con += 1
                
print(con);

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

int main() {
  int h, w;
  cin >> h >> w;
  int C[w][h], R[w][h];
  for (int j = 0; j < h; j++) {
      for (int i = 0; i < w; i++) {
      cin >> C[i][j];
    }
  }
  int result = 0;
  for (int j = 0; j < h; j++) {
    for (int i = 0; i < w; i++) {
      if (!C[i][j]) {
        int pre_area = 0;
        if (i && j) {
          pre_area = min(min(R[i-1][j-1], R[i-1][j]),
                         R[i][j-1]);
        }
        R[i][j] = pre_area + 1;
      } else {
        R[i][j] = 0;
      }
      result = max(result, R[i][j]);
    }
  }
  cout << (result*result) << endl;
  return 0;
}



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

#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = (int)1e6 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;

void megaRandom() {
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  srand(FOR);
}

int n, k, a[N];
bool ok[3];
int mx;

int main() {
	megaRandom();
	scanf("%d%d", &n, &k);
	int gcd = 0;
	for(int i = 1; i <= n; i ++) {
		scanf("%d", &a[i]);
		gcd = __gcd(gcd, a[i]);
		mx = max(mx, a[i]);
	}
	if(k > mx) printf("IMPOSSIBLE");
	else {
		if(k % gcd == 0) printf("POSSIBLE");
		else printf("IMPOSSIBLE");
	}
	return 0;         
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;

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

	int n;
	cin >> n;
	vi q(n);
	rep(i,0,n){
		int j;
		cin >> j;
		q[j-1] = i;
	}

	vi dp(n);
	rep(i,0,n){
		dp[i] = 1;
		if(i > 0 && q[i]>q[i-1]) dp[i] = dp[i-1]+1;
	}
	int ans = n;
	rep(i,0,n) ans = min(ans, n-dp[i]);
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

#define INF (1 << 30)

int main()
{
	int N, M;

	cin >> N >> M;

	vector<int> D(N);
	vector<int> C(M);

	for (int i = 0; i < N; i++)
		cin >> D[i];

	for (int i = 0; i < M; i++)
		cin >> C[i];

	vector<vector<int> > dp(M + 1, vector<int>(N + 1, INF));

	dp[0][0] = 0;


	for (int i = 1; i <= M; i++)
	{
		for (int j = 0; j <= N; j++)
		{
			if (j == 0)
			{
				dp[i][j] = dp[i - 1][j];
			}
			else
			{
				dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + C[i - 1] * D[j - 1]);
			}
		}
	}

	cout << dp[M][N] << endl;

	return 0;
}

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

const int mod = (int) 1e9 + 7;
const int MaxN = 1002;
ll a[MaxN];
ll b[MaxN];
ll cnts[MaxN][MaxN];

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

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

	sort(a, a + n);
	sort(b, b + m);
	for (int i = 0; i + 1 < n; ++i)
		if (a[i] == a[i + 1]) {
			cout << 0;
			return 0;
		}

	for (int j = 0; j + 1 < m; ++j)
		if (b[j] == b[j + 1]) {
			cout << 0;
			return 0;
		}
	cerr << "Test" << endl;

	if (a[n - 1] != n * m || b[m - 1] != n * m) {
		cout << 0;
		return 0;
	}
	cerr << "Test" << endl;

	for (ll x = 1, i = 0, j = 0; x <= n * m; ++x) {
		while (a[i] < x)
			++i;
		while (b[j] < x)
			++j;
		assert(i < n && j < m);
		if (x != a[i] && x != b[j])
			cnts[i][j]++;
	}


	ll i = n - 1, j = m - 1;
	ll placed = 0;
	ll ans = 1;
	while (i >= 0 && j >= 0) {
		placed++;
		if (a[i] < b[j])
			ans *= (m - j);
		if (a[i] > b[j])
			ans *= (n - i);
		ans %= mod;
		for (ll &cnt = cnts[i][j]; cnt > 0; --cnt) {
			ans *= (n - i) * (m - j) % mod - placed;
			ans %= mod;
			placed++;
		}

		if (i && j && a[i - 1] == b[j - 1])
			--i, --j;
		else if (!j || (i && a[i - 1] > b[j - 1]))
			--i;
		else
			--j;
	}
	cout << (ans % mod + mod) % mod << endl;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			assert(!cnts[i][j]);
	return 0;
}


Measured memory_bytes: 5248
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main(void){
    int n;
    string s;
    cin >> n >> s;
    int count = 0;
    for(int j=0; j<n; j++){
        if(s[j] != '#'){
            count++;
        }
    }
    int ans = count;
    for(int i=0; i<n; i++){
        if(s[i] == '.'){
            count--;
        }else if(s[i] == '#'){
            count++;
        }
        if(count < ans) ans = count;
    }
    cout << ans << endl;
}

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

using namespace std;

int main(){
 int h,w;
  cin >> h >> w;
  string a;
  int res=0;
  for(int i=0;i<h;i++){
    cin >> a;
   for(int j=0;j<w;j++){
    if(a[j]=='#') res++;
   }
  }
 
  if(res==h+w-1) cout << "Possible" << endl;
  else  cout << "Impossible" << endl;

}


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



int main() {
  int k,n;
  cin >> k >> n;
  int a[n];
  for(int i=0;i<n;i++) cin >> a[i];
  int MAX = 0,index;
  for(int i=0;i<n;i++){
      int before = i-1;
      if(before < 0) before += n;
      int sa = a[i] - a[before];
      if(sa < 0) sa+=k;
      if(sa > MAX){
          MAX = sa;
          index = i;
      }
  }
  int sum = k - MAX;

  cout << sum << endl;
  return 0;


}


Measured memory_bytes: 1024
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;//例: VVI dp(10, vector<int>(10, INF);
typedef priority_queue<int, vector<int>, less<int> > QUE_int;
const int INF = 2 * pow(10, 9) + 1;//+1しないとREになるかも(out of rangeになるんかな?? )

vector<int> dx = { -1, 0, 1, 0, -1, -1, 1, 1 };
vector<int> dy = { 0, -1, 0, 1, -1, 1, -1, 1 };

int main(void) {
	
	string S, T;
	cin >> S >> T;

	int A, B;
	cin >> A >> B;

	string U;
	cin >> U;

	if (U == S) {
		cout << A - 1 << " " << B << endl;
		return 0;
	}
	if (U == T) {
		cout << A << " " << B - 1 << endl;
		return 0;
	}
}


Measured memory_bytes: 256
N = int(input())
B = [[[0] * 10 for _ in range(3)] for _ in range(4)]

for _ in range(N):
    b, f, r, v = map(int, input().split())
    B[b - 1][f - 1][r - 1] += v

for i, b in enumerate(B):
    if i != 0:
        print('#' * 20)
    for f in b:
        print(' ', end='')
        print(*f)


Measured memory_bytes: 5624
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printv(x) for(int i = 0; i < x.size(); i++){ cout << (x[i]) << " "; } cout << endl; 
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printaa(x) for(int i = 0; i < (sizeof(x)/sizeof(x[0])); i++){ for(int j = 0; j < (sizeof(x[0])/sizeof(x[0][0])); j++){ cout << x[i][j] << " ";} cout << endl;}
#define INF (1e9)
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;

using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    ll a[100001];
    ll x;
    cin >> N >> x;
    rep(i,0,N) cin >> a[i];
    ll ans = 0;
    if(a[0] > x){
        ans += a[0] - x;
        a[0] = x;
    }
    rep(i,1,N){
        if(a[i] + a[i-1] > x){
            ans += a[i] + a[i-1] - x;
            a[i] -= (a[i] + a[i-1] - x);
        }   
    }
    print(ans);


}


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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

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

    int ans=123456789;

    for(int i=-100; i<=100; ++i)
    {
        int t=0;
        rep(j,n) t+=(a[j]-i)*(a[j]-i);
        ans=min(ans,t);
    }

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


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

int main(){
    int N[100002]={};
    int n;
    int tmp;
    int max=0;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> tmp;
        N[tmp]++;
        N[tmp+1]++;
        N[tmp+2]++;
    }
    for(int i=0; i<100002; i++){
        if(N[i] > max)
            max = N[i];
    }
    cout << max;
    
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int main(void)
{
    bool judge = false;
    string a,b;
    cin >> a >> b;
    if(a.size() == b.size())
    {
        for(int i = 0;i < a.size();i++)
        {
            if(a[i] < b[i]){cout << "LESS" << endl; judge = true; break;}
            else if(a[i] > b[i]){cout << "GREATER" << endl; judge = true; break;}
        }
        if(!judge){cout << "EQUAL" << endl;}
    }
    else if(a.size() < b.size()){cout << "LESS" << endl;}
    else{cout << "GREATER" << endl;}
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>

using namespace std;

#define MAX 20

int W,H;
int arr[MAX][MAX];
int dp[MAX][MAX];
const int dx[] = {-1,0,1};
const int dy[] = {1,1,1};

bool inField(int y,int x){
  return 0 <= y && y < H && 0 <= x && x < W;
}

int solve(int y,int x){
  if(y == H-1){
    if(arr[y][x] == 0 || arr[y][x] == 2){
      return 1;
    }else{
      return 0;
    }
  }
  if(dp[y][x] != -1) return dp[y][x];

  int res = 0;
  if(arr[y][x] != 2){
    for(int i = 0 ; i < 3 ; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(!inField(ny,nx)) continue;
      if(arr[ny][nx] == 1) continue;
      if(arr[ny][nx] == 0){
        res += solve(ny,nx);
      }else{
        if(x == nx){
          res += solve(ny,nx);
        }
      }
    }
  }else{
    int nx = x, ny = y + 2;
    if(!inField(ny,nx)) return 1;
    if(arr[ny][nx] == 1) return 0;
    res += solve(ny,nx);
  }
  return dp[y][x] = res;
}

int main(){
  while(cin >> W >> H, (W | H)){
    for(int i = 0 ; i < H ; i++){
      for(int j = 0 ; j < W ; j++){
        cin >> arr[i][j];
        dp[i][j] = -1;
      }
    }
    int res = 0;
    for(int i = 0 ; i < W ; i++){
      if(arr[0][i] == 0){
        res += solve(0,i);
      }
    }
    cout << res << endl;
  }

  return 0;
}

Measured memory_bytes: 1164
# abc107 B
h, w = gets.split.map(&:to_i)
c = h.times.map {
  gets.chomp.chars
}
# puts c.map{|x| x.join }.join("\n")
c.reject!{|cc|cc.all?{|x|x == '.'}}
c = c.transpose
c.reject!{|cc|cc.all?{|x|x == '.'}}
c = c.transpose
puts c.map{|x| x.join }.join("\n")


Measured memory_bytes: 2556
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vs = vector<string>;
#define  rep(i,n) for(ll i = 0; i < (n); ++i)
#define  red(i,n) for(ll i = (n)-1; i >= 0; --i)
#define  all(a)   begin(a),end(a)
#define  pb(a)    push_back(a)
#define  yn     cout<<"Yes\n"; else cout<<"No\n";
inline ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
const int INF=1000000009;
const ll LINF = 1e18;

int main()
{
    int n,x,q=0;
    cin>>n;
    map<int,int> a;
    rep(i,n)cin>>x,a[x]++;
    for(auto x:a){
        if(x.first>x.second) q+=x.second;
        if(x.first<x.second) q+=x.second-x.first;
    }
    cout<<q<<endl;
    
    return 0;
}


Measured memory_bytes: 4736
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
#include <list>
#include <time.h>
using namespace std;
#define pi pair<int,int>
#define pl pair<long long,long long>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}

 
int main(){
    string s,t; cin >> s;
    for (int i = 0; i < s.size()-1; i++){
        if (s[i] == 'B' && s[i+1] == 'C'){
            t += 'D';
            i++;
        } else {
            t += s[i];
        }
    }
    int ca = 0;
    long long ans = 0;
    for (int i = 0; i < t.size(); i++){
        if (t[i] == 'A') ca++;
        else if (t[i] == 'D') ans += ca;
        else ca = 0;
    }
    cout << ans << endl;
}




Measured memory_bytes: 776