akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int getcount(char* a,int aend,char comparison){
	int numOfR=0;
	rep(i,aend){
		if(a[i]==comparison) numOfR++;
	}
	return numOfR;
}

int main() {
	int ans=0;

	int n;
	cin >> n;
	char a[n];
	rep(i,n) cin >> a[i];

	//敷居のため、Rの数を求める
	int devide = getcount(a,n,'R');

	//敷居より左側のWの数を求める
	ans = getcount(a,devide,'W');

	cout << ans << endl;
}

Measured memory_bytes: 3800
#include <bits/stdc++.h>
using namespace std;
// make_tuple emplace_back next_permutation push_back make_pair second first
// setprecision

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif

using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

struct Problem {
  LL a, b, lb, ub;
  set<pair<LL, LL>> rangeOr, canMake;
  void insert_(set<pair<LL, LL>> &st, pair<LL, LL> t) {
    DBG(t)
    auto it = st.lower_bound(make_pair(t.first, 0ll));
    if (it != st.begin()) {
      auto it2 = it;
      it2--;
      if (it2->second >= t.first) {
        pair<LL, LL> tmp = *it2;
        tmp.second = max(tmp.second, t.second);
        st.erase(it2);
        it = st.insert(it, tmp);
      } else {
        it = st.insert(it, t);
      }
    } else {
      it = st.insert(it, t);
    }
    auto nxt = it;
    nxt++;
    if (nxt != st.end() && it->second >= nxt->first) {
      pair<LL, LL> tmp = *it;
      tmp.second = max(tmp.second, nxt->second);
      st.erase(it);
      st.erase(nxt);
      st.insert(tmp);
    }
  }
  void restrictRange(int digit) {
    if (digit >= 60) return;
    set<pair<LL, LL>> res;
    LL interval = (1ll << (digit + 1));
    DBG(digit, canMake)
    for (auto p : canMake) {
      LL a = p.first, b = p.second;
      for (LL j = (a + interval) / interval * interval; j < b + interval;
           j += interval) {
        insert_(res, {a % interval,
                      (min(b, j) % interval == 0 ? interval
                                                 : min(b, j) % interval)});
        a = j;
      }
    }
    swap(canMake, res);
    DBG("r", digit, canMake)
  }
  void mask(int digit) {
    set<pair<LL, LL>> res;
    LL interval = (1ll << (digit));
    DBG(digit, canMake)
    for (auto p : canMake) {
      LL a = p.first, b = p.second;
      DBG(a, b)
      for (LL j = (a + interval) / interval * interval; j < b + interval;
           j += interval) {
        DBG(a, b, j)
        if (((a >> (digit)) & 1) == 0) {
          insert_(res, {a % interval,
                        (min(b, j) % interval == 0 ? interval
                                                   : min(b, j) % interval)});
        }
        a = j;
      }
    }
    swap(canMake, res);
    DBG("m", digit, canMake)
  }
  void solve() {
    cin >> a >> b;
    rangeOr.emplace(a, b + 1);
    canMake.emplace(a, b + 1);
    ub = 1;
    while (ub <= b) ub <<= 1;
    for (int i = 60; i >= 0; --i) {
      LL bUpper = (b >> i) << i;
      DBG(i, (1ll << i), (b >> i))
      restrictRange(i);
      if ((1ll << i) > b or ((b >> i) & 1) == 1) continue;
      DBG(i, bUpper, canMake)
      for (auto p : canMake) {
        insert_(rangeOr, {bUpper + p.first, bUpper + p.second});
      }
      mask(i);
    }
    LL ans = 0;
    for (auto p : rangeOr) {
      DBG(p)
      ans += p.second - p.first;
    }
    cout << ans << endl;
  }
};

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  Problem p;
  p.solve();
  return 0;
}


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

using namespace std;
typedef long long ll;

const ll N = 3010;
ll dp[N][N];

int main() {
    ios_base::sync_with_stdio(false);

    string s, t;
    cin >> s >> t;
    ll n = s.length(), m = t.length();
    for (ll i = 0; i <= n; i++) {
        for (ll j = 0; j <= m; j++) {
            if (i == 0 || j == 0) dp[i][j] = 0;
            else if (s[i - 1] == t[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    ll len = dp[n][m];
    string ans;
    ll i = n, j = m;
    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            ans += s[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) i--;
        else j--;
    }
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < len; i++) cout << ans[i];

    return 0;
}


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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

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

  CIN(A, B, C, D);
  string ans;
  if (A + B < C + D) ans = "Right";
  else if (A + B == C + D) ans = "Balanced";
  else ans = "Left";

  cout << ans << endl;

  return 0;
}




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

using namespace std;

int main(void) {
  int n, k;
  cin >> n >> k;
  int l[n];
  for(int i = 0; i < n; i++) {
    cin >> l[i];
  }

  sort(l, l + n);
  int sum = 0;
  for(int i = 0; i < k; i++) {
    sum += l[n - 1 - i];
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <map>
using namespace std;

int main() {
    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);

    int s, c;
    map<int, int> b;
    for (int i=0; i<m; i++) {
        scanf("%d", &s);
        scanf("%d", &c);
        if (b.count(s)) {
            if (b[s] != c) {
                printf("-1\n");
                return 0;
            }
        }
        b[s] = c;
    }

    if (n > 1) {
        if (b.count(1) and b[1] == 0) {
            printf("-1\n");
            return 0;
        }
        if (not b.count(1)) {
            b[1] = 1;
        }
    }

    int ans[n] = {};
    for(auto i = b.begin(); i != b.end(); ++i) {
        ans[i->first - 1] = i->second;
    }
    for (int i=0; i<n; i++) {
        printf("%d", ans[i]);
    }
    printf("\n");
}

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

const int mod=998244353,N=1000010,iv2=(mod+1>>1);
int jc[N],inv[N],n,m,ans,mi[N];

int C(int a,int b)
{
	if (a<b||b<0) return 0;
	return 1ll*jc[a]*inv[b]%mod*inv[a-b]%mod;
}

int quickmi(int a,int b)
{
	int t=1;
	for (; b; b>>=1,a=1ll*a*a%mod)
		if (b&1) t=1ll*t*a%mod;
	return t;
}

int calc(int n,int m)
{
	int ans=C(n+m,n)-C(n+m,n-1);
	return (ans<0?ans+mod:ans);
}

int getfi(int n)
{
	if (n==0) return 0;
	return (1ll*jc[2*n-1]*inv[n-1]%mod*inv[n-1]%mod+mi[n-1])*iv2%mod;
}

int getfo(int n)
{
	if (n<=1) return 0;
	return 1ll*jc[2*n-3]*inv[n-2]%mod*inv[n-2]%mod;
}

int getgi(int n) {return C(2*n-2,n-1);}
int getgo(int n) {return 1ll*(C(2*n-2,n-1)+(n==1))*iv2%mod;}

int solve(int n,int m)
{
	n++,m++;
	int ans=0;
	if (m>=n)
	{
		for (int i=1; i<=n; i++)
			ans=(ans+1ll*getgo(i)*calc(n-i,m-i)%mod*(n-i+m-i+1)+1ll*getfo(i)*calc(n-i,m-i))%mod;
	} else
	{
		for (int i=1; i<=m; i++)
			ans=(ans+1ll*getfi(i)*calc(m-i,n-i-1))%mod;
	}
	return ans;
}

int main()
{
	jc[0]=mi[0]=1;
	for (int i=1; i<N; i++) mi[i]=4ll*mi[i-1]%mod;
	for (int i=1; i<N; i++) jc[i]=1ll*jc[i-1]*i%mod;
	inv[N-1]=quickmi(jc[N-1],mod-2);
	for (int i=N-1; i; i--) inv[i-1]=1ll*inv[i]*i%mod;
	scanf("%d%d",&n,&m);
	if (n==0||m==0) return printf("%d\n",n+m),0;
	int ans=solve(m,n-1)+solve(n,m-1);
	if (ans>=mod) ans-=mod;
	for (int i=1; i<=n&&i<=m; i++) 
		ans=(ans+1ll*C(i+i-1,i-1)*C(n-i+m-i,n-i))%mod;
	ans=1ll*ans*quickmi(C(n+m,m),mod-2)%mod;
	return printf("%d\n",ans),0;
}


/*
sigma{i=0..n}sigma{j=0..m}C(i+j,i)*C(n+m-i-j,n-i)*max(i,j)/(i+j)/C(n+m,n)
(0,0)->(n,m-1)----without y<=x-2
(0,0)->(n-1,m)----without y>=x+1
fi[1]=1,gi[1]=1,fo[1]=0,go[1]=1
fi[n]=sigma{i=1..n}fo[i]*c[n-i]+go[i]*c[n-i]*(2*(n-i)+1)
gi[n]=sigma{i=1..n}go[i]*c[n-i]
fo[n]=sigma{i=1..n-1}fi[i]*c[n-i-1]
go[n]=sigma{i=1..n-1}gi[i]*c[n-i-1]

GI=x/sqrt(1-4x)          {C(2n-2,n-1)}
GO=(x+xsqrt(1-4x))/2sqrt(1-4x)  {[C(2n-2,n-1)+(n==1)]/2}
FI=2x^2/(4x+sqrt(1-4x)-1)(1-4x) {[(2n-1)!/(n-1)!(n-1)!+4^(n-1)]/2}
FO=x^2/sqrt(1-4x)(1-4x) {(2k-3)!/(k-2)!(k-2)!}
*/

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

#define iin(x) scanf("%d", &x)
#define lin(x) scanf("%lld", &x)
#define fin(x) scanf("%lf", &x)

#define iout(x) printf("%d", x)
#define lout(x) printf("%d", x)
#define fout(x) printf("%.10f", x)
#define _ putchar(' ')
#define endl puts("")

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

#define PI acos(-1)

typedef struct {
  double x, y;  
} Point;

Point triPoint(Point s, Point t) {
  Point p;
  p.x = (t.x-s.x)*cos(PI/3) - (t.y-s.y)*sin(PI/3) + s.x;
  p.y = (t.x-s.x)*sin(PI/3) + (t.y-s.y)*cos(PI/3) + s.y;
  return p;
}

void Koch(int n, Point p1, Point p2) {
  if(n == 0) return;
  Point s = (Point){(2*p1.x+p2.x)/3, (2*p1.y+p2.y)/3};
  Point t = (Point){(p1.x+2*p2.x)/3, (p1.y+2*p2.y)/3};
  Point u = triPoint(s, t);
  Koch(n-1, p1, s);
  fout(s.x),_,fout(s.y),endl;
  Koch(n-1, s, u);
  fout(u.x),_,fout(u.y),endl;
  Koch(n-1, u, t);
  fout(t.x),_,fout(t.y),endl;
  Koch(n-1, t, p2);
}

int main() {
  int n;
  iin(n);
  fout(0.0),_,fout(0.0),endl;
  Koch(n, (Point){0, 0}, (Point){100, 0});
  fout(100.0),_,fout(0.0),endl;
  return 0;
}

Measured memory_bytes: 652
n=gets.to_i
P=gets.split.map(&:to_i)
cnt = 0
(1...(n-1)).each do |i|
  if P[i-1] < P[i] && P[i+1] > P[i]
    cnt += 1
  elsif  P[i-1] > P[i] && P[i+1] < P[i]
    cnt += 1
  end
end
p cnt

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int n, m, c;
    cin >> n >> m >> c;
    vector<int> b(m);
    rep(i, m) cin >> b[i];
    int ans = 0;
    rep(i, n)
    {
        int sum = c;
        rep(j, m)
        {
            int a;
            cin >> a;
            sum += a * b[j];
        }
        if (sum > 0)
            ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s;
int main ()
{
	  cin>>s;
	
	int n=s.size();
	int cnt=0;
	for(int i=0;i<n;i++){
		if(s[i]!=s[n-1-i])
		cnt++;
		
	}
	
	cout<<cnt/2<<endl;
	


}



Measured memory_bytes: 3628
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
using namespace std;

const int MAX_N = 2005;
int N, A[MAX_N];

bitset<MAX_N * MAX_N> f[2];

int main() {
  scanf("%d", &N);
  int sum = 0, o = 0;
  
  f[0][0] = 1;
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &A[i]);
    sum += A[i], o ^= 1;
    f[o] = (f[o ^ 1] << A[i]) | f[o ^ 1];
  }
  
  int x = (sum + 1) / 2;
  while (!f[o][x]) x++;
  printf("%d\n", x);
  return 0;
}


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

int main() {
  int N;
  cin >> N;
  if(N == 1){
    cout << 0 << endl;
  }else if(N == 2){
    cout << 2 << endl;
  }
  if(N >= 3){
    ll A = 1;
    ll B = 1;
    ll C = 1;
    rep(i, N){
      A *= 10;
      A = A % mod; 
    }
    rep(i, N){
      B *= 9;
      B = B % mod;
    }
    rep(i, N){
      C *= 8;
      C = C % mod;
    }
    ll D = A - (2 * B) + C;
    if(D > 0){
      cout << D; 
    }else{
      while(D < 0){
      D += mod;
      }
     cout << D;
    }
  }
}

Measured memory_bytes: 3632
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.math.BigInteger;
    
public class Main{

static final InputStream in=System.in;
static final PrintWriter out=new PrintWriter(System.out);
static final int INF=Integer.MAX_VALUE/2;
static final long LINF=Long.MAX_VALUE/2;

public static void main(String[] args) throws IOException{
Scanner ir=new Scanner(in);
while(ir.hasNextInt()){
int N=ir.nextInt();
if(N==0) break;
int acnt,bcnt;
acnt=bcnt=0;
while(N-->0){
int a=ir.nextInt();
int b=ir.nextInt();
if(a>b) acnt+=(a+b);
else if(a==b){
acnt+=a;
bcnt+=b;
}
else bcnt+=(a+b);
}
out.println(acnt+" "+bcnt);
}
out.flush();
}

static class InputReader {
private InputStream in;
private byte[] buffer=new byte[1024];
private int curbuf;
private int lenbuf;

public InputReader(InputStream in) {this.in=in;}
  
public int readByte() {
if(lenbuf==-1) throw new InputMismatchException();
if(curbuf>=lenbuf){
curbuf= 0;
try{
lenbuf=in.read(buffer);
}
catch (IOException e) {
throw new InputMismatchException();
}
if(lenbuf<=0)
return -1;
}
return buffer[curbuf++];
}

public boolean isSpaceChar(int c){return !(c>=33&&c<=126);}

private int skip() {int b; while((b = readByte())!=-1&&isSpaceChar(b)); return b;}

public String next() {
int b=skip();
StringBuilder sb=new StringBuilder();
while(!isSpaceChar(b)){
sb.appendCodePoint(b);
b=readByte();
}
return sb.toString();
}
 
public int nextInt() {
int c=readByte();
while (isSpaceChar(c)) c=readByte();
boolean minus=false;
if (c=='-') {
minus=true;
c=readByte();
}
int res=0;
do{
if(c<'0'||c>'9') throw new InputMismatchException();
res=res*10+c-'0';
c=readByte();
}while(!isSpaceChar(c));
return (minus)?-res:res;
}

public long nextLong() {
int c=readByte();
while (isSpaceChar(c)) c=readByte();
boolean minus=false;
if (c=='-') {
minus=true;
c=readByte();
}
long res = 0;
do{
if(c<'0'||c>'9') throw new InputMismatchException();
res=res*10+c-'0';
c=readByte();
}while(!isSpaceChar(c));
return (minus)?-res:res;
}

public int[] toIntArray(int n){
int[] a=new int[n];
for(int i=0;i<n;i++) a[i]=nextInt();
return a;
}
}
}

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

#define fst first
#define snd second
#define mkp make_pair
typedef pair<int, int> pii;
const int MAXN = 2010;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch=='-') f=-1;
	for(; isdigit(ch); ch = getchar()) x = (x*10)+(ch^48);
	return x * f;
}

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

int n, a[MAXN], indeg[MAXN];
int st[MAXN], to[MAXN*MAXN];
int nxt[MAXN*MAXN], e;
inline void Add(int u, int v) {
	to[++e] = v, nxt[e] = st[u];
	st[u] = e, indeg[v]++;
}

bool vis[MAXN];
int dep[MAXN];
vector<int> G[MAXN];

bool cmp(const int &x, const int &y) {
	return a[x] < a[y];
}

inline void dfs(int u, int fa) {
	vis[u] = true;
	int i;
	sort(G[u].begin(), G[u].end(), cmp);
	for(i = 0; i < (int)G[u].size(); i++) {
		int v = G[u][i];
		if(v == fa) continue;
		if(vis[v]) {
			if(dep[v] > dep[u]) Add(u, v);
			continue;
		}
		dep[v] = dep[u]+1;
		Add(u, v), dfs(v, u);
	}
}

priority_queue<pii> q;

int main() {

	int i, j;
	n = read();
	generate(a+1, a+n+1, read);
	sort(a+1, a+n+1);

	for(i = 1; i <= n; i++) 
		for(j = 1; j < i; j++) 
			if(gcd(a[i], a[j]) != 1) 
				G[i].push_back(j), G[j].push_back(i);

	for(i = 1; i <= n; i++) 
		if(!vis[i]) dfs(i, 0);

	for(i = 1; i <= n; i++)
		if(!indeg[i]) q.push(mkp(a[i], i));
	
	while(!q.empty()) {
		int u = q.top().snd;
		printf("%d ", a[u]);
		q.pop();
		for(i = st[u]; i; i = nxt[i]) {
			int v = to[i];
			indeg[v]--;
			if(!indeg[v]) q.push(mkp(a[v], v));
		}
	}
	printf("\n");
	return 0;
}


Measured memory_bytes: 31104
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <regex>
#include <iomanip>
#include <climits>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;

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

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

    vector<ll> P(N);
    for (ll i = 0; i < N; i++)
    {
        cin >> P[i];
    }
    
    bool ok = false;
    for (ll i = 0; i < N; i++)
    {
        for (ll j = i; j < N; j++)
        {
            auto P_copy = P;
            swap(P_copy[i], P_copy[j]);

            bool asc = true;
            for (ll k = 1; k < N; k++)
            {
                if (P_copy[k - 1] > P_copy[k]) {
                    asc = false;
                }
            }
            ok |= asc;
        }
    }
    cout << (ok ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    primes = get_primes(55555)
    out = []
    num = 0
    for prime in primes:
        if prime%5 == 1:
           out.append(prime)
           num += 1
        if n == num:
            print(*out)
            return

def get_primes(x):
    if x < 2:
        return []
    if x == 2:
        return [2]
    limit = x**0.5
    nums = list(range(3, x+1, 2))
    divider = 3
    dividers = []
    while limit >= divider:
        dividers.append(divider)
        nums = [num for num in nums if num%divider]
        divider = nums[0]
    return dividers+nums
        
if __name__ == "__main__":
    main()

Measured memory_bytes: 4468
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	Info(ll arg_value){
		value = arg_value;
	}
	bool operator<(const struct Info &arg) const{
		return value < arg.value;
	};
	ll value;
};

int main(){

	int N;
	ll P,Q,tmp;

	scanf("%d %lld %lld",&N,&P,&Q);

	priority_queue<Info> PQ;

	for(int i = 1; i <= N; i++){
		scanf("%lld",&tmp);
		PQ.push(Info(tmp+P*(i-1)));
	}

	ll sum = 0;
	ll num_self = N;
	ll ans = P*(num_self*Q + num_self*(num_self-1));

	while(!PQ.empty()){
		num_self--;
		sum += PQ.top().value;
		ans = max(ans,sum+P*(num_self*Q+num_self*(num_self-1)));
		PQ.pop();
	}

	for(ll i = 1; i <= N-1; i++)ans -= P*i;

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

	return 0;
}

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

int h, w;
char s[50][50];
string ans = "Yes";

bool isWhite(int y, int x) {
    if (y == -1 || y == h || x == -1 || x == w) return true;
    if (s[y][x] == '.') return true;
    return false;
}

void updateAns(int y, int x) {
    if (isWhite(y, x-1) && isWhite(y, x+1) && isWhite(y+1, x) && isWhite(y-1, x)) {
        ans = "No";
    }
}

int main() {
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> s[i][j];
        }
    }
    // #黒 .白
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '#') {
                updateAns(i, j);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

class Space {
public:
    Space(int64_t l_in, int64_t r_in) : l(l_in), r(r_in) {
        this->v = std::min(this->l, this->r);
    }
#if 0
    bool operator< (const Space& lhs, const Space& rhs) {
        return lhs.v < rhs.v;
    }
#endif
    int64_t l;
    int64_t r;
    int64_t v; 
};

struct Order {
    bool operator() (const Space& lhs, const Space& rhs) {
        return lhs.v < rhs.v;
    }
};

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

    int64_t A[N];
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::sort(A, A + N, std::greater<int64_t>());

    int64_t ans = 0;
    std::priority_queue<Space, std::vector<Space>, Order> queue;
    for (int i = 0; i < N; ++i) {
        if (i == 0) {
            queue.push(Space(A[i], A[i]));
            continue;
        }

        const Space s = queue.top();
        ans += s.v;
        queue.pop();

        queue.push(Space(s.l, A[i]));
        queue.push(Space(A[i], s.r));
    }

    std::cout << ans << std::endl;

    return 0;
}


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

int main()
{
    long long a,b,n;

    cin >> a >> b >> n;

    if(n < b)
    {
        cout << (a * n) / b;
    }
    else
    {
        cout << (a * (b - 1) / b);
    }
    
}


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

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<vector<pair<long, long>>> e(N+1, vector<pair<long, long>>{}); // dest, weight
    for(int i=0; i<N-1; ++i){
        long u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }

    vector<int> c(N+1);
    int count = 0;
    function<void(int, int, int, int)> solve = [&](int current, int prev_node, int prev_color, int prev_dist){
        c[current] = (prev_color+prev_dist) % 2;
        ++count;
        if(count>=N) return;
        for(auto p : e[current]){
            if(p.first!=prev_node){
                solve(p.first, current, c[current], p.second);
            }
        }
    };
    solve(1, 0, 0, 0);
    for(int i=1; i<=N; ++i){
        cout << c[i] << endl;
    }
}


Measured memory_bytes: 11264
#include<stdio.h>
int main(){
  int x,y,i,r,tmp,max;
  scanf("%d %d",&x,&y);
  if(y > x){
    tmp = x;
    x = y;
    y = tmp;
  }
  r = x % y;
  if(r == 0) max = x;
  else{
    for(i = 1;i <= r; i++){
      if(r%i == 0){
        if(y % i ==0){
          max = i;
        }
      }
    }
  }
  printf("%d\n",max);
  return 0;
}



Measured memory_bytes: 2124
import sys
import math
import bisect
import heapq
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
Bl=[[] for i in range(10**5+5)]

for i in range(N):
    A,B=nm()
    Bl[A].append(-B)

now=[]
if(Bl[0]!=[]):
    for i in range(len(Bl[0])):
        heapq.heappush(now,Bl[0][i])

ans=0
for i in range(1,M+2):
    if(now!=[]):
        max_val=heapq.heappop(now)
        ans+=max_val
    if(Bl[i]!=[]):
        for j in range(len(Bl[i])):
            heapq.heappush(now,Bl[i][j])

print(-ans)


Measured memory_bytes: 18012
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,k,l,i,sum=0,counter=0;
cin>>a;

for(i=1;i<=a;i++)
{
    if(i%2==0)
    {
        sum++;
    }
    else{
        counter++;
    }

}

cout<<sum*counter<<endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

#define int i64

int w,h;

vector<int> ans;

signed main(){
	while(cin >> w >> h,w || h){
		vector<vector<int>> fie(h,vector<int>(w,0));
		vector<P> dust;
		int sx,sy;
		for(int i = 0;i < h;i++){
			string s;
			cin>> s;
			for(int j = 0;j < w;j++){
				if(s[j] == '*'){
					dust.push_back({i,j});
					fie[i][j] = dust.size();
				}
				if(s[j] == 'x'){
					fie[i][j] = -1;
				}
				if(s[j] == 'o'){
					sx = i;
					sy = j;
				}
			}
		}
		using P2 = pair<int,P>;
		vector<vector<int>> dist(dust.size(),vector<int>(dust.size() , 1e9));

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

		for(int s = 0;s < dust.size();s++){
			queue<P2> que;
			que.push({0,dust[s]});
			vector<vector<int>> vis(h,vector<int>(w,0));
			vis[dust[s].first][dust[s].second] = 1;
			while(!que.empty()){
				int d = que.front().first;
				P p = que.front().second;
				if(fie[p.first][p.second] > 0){
					dist[s][fie[p.first][p.second] - 1] = d;
				}
				que.pop();
				for(int i = 0;i < 4;i++){
					int nx = p.first + dx[i];
					int ny = p.second + dy[i];
					if(0 <= nx && nx < h && 0 <= ny && ny < w && fie[nx][ny] != -1 && vis[nx][ny] == 0){
						vis[nx][ny] = 1;
						que.push({d + 1,{nx,ny}});
					}
				}
			}
		}

		vector<vector<int>> dp(1 << dust.size(),vector<int>(dust.size(),1e9));
		{
			queue<P2> que;
			que.push({0,{sx,sy}});
			vector<vector<int>> vis(h,vector<int>(w,0));
			vis[sx][sy] = 1;
			while(!que.empty()){
				int d = que.front().first;
				P p = que.front().second;
				if(fie[p.first][p.second] > 0){
					dp[(1 << (fie[p.first][p.second] - 1))][fie[p.first][p.second] - 1] = d;
				}
				que.pop();
				for(int i = 0;i < 4;i++){
					int nx = p.first + dx[i];
					int ny = p.second + dy[i];
					if(0 <= nx && nx < h && 0 <= ny && ny < w && fie[nx][ny] != -1 && vis[nx][ny] == 0){
						vis[nx][ny] = 1;
						que.push({d + 1,{nx,ny}});
					}
				}
			}
		}

		for(int i = 1;i < (1 << dust.size()) - 1;i++){
			for(int j = 0;j < dust.size();j++){
				if(i & (1 << j)) continue;
				for(int k = 0;k < dust.size();k++){
					if(j == k) continue;
					if((i & (1 << k))){
						//j <- k
						dp[i | (1 << j)][j] = min(dp[i | (1 << j)][j] , dp[i][k] + dist[k][j]);
					}
				}
			}
		}

		int result = 1e9;
		for(int i = 0;i < dust.size();i++){
			result = min(result , dp[(1 << dust.size()) - 1][i]);
		}
		if(result >= 1e9) result = -1;
		ans.push_back(result);
	}
	for(int a : ans){
		cout << a << endl;
	}
}



Measured memory_bytes: 3100
package main

import (
        "bufio"
        "fmt"
        "os"
)

func solution(n, m int, a, b []int) (string, []int) {
        const MAX = 1 << 31
        g := make([][]int, n)
        for i := 0; i < m; i++ {
                v, w := a[i]-1, b[i]-1
                g[v] = append(g[v], w)
                g[w] = append(g[w], v)
        }
        queue := make([]int, 0, n)

        dist := make([]int, n)
        for i := range dist {
                dist[i] = MAX
        }

        prev := make([]int, n)
        for i := range prev {
                prev[i] = -1
        }

        queue = append(queue, 0)
        dist[0] = 0
        prev[0] = 0

        for len(queue) > 0 {
                v := queue[0]
                queue = queue[1:]
                for _, u := range g[v] {
                        if dist[u] != MAX {
                                continue
                        }
                        dist[u] = dist[v] + 1
                        prev[u] = v
                        queue = append(queue, u)
                }

        }

        for _, t := range prev {
                if t == -1 {
                        return "No", []int{}
                }
        }
        for i := 1; i < n; i++ {
                prev[i]++
        }
        return "Yes", prev[1:]
}

func main() {
        r := bufio.NewReader(os.Stdin)
        var n, m int
        fmt.Fscan(r, &n, &m)
        a := make([]int, 0, m)
        b := make([]int, 0, m)
        for i := 0; i < m; i++ {
                var ta, tb int
                fmt.Fscan(r, &ta, &tb)
                a = append(a, ta)
                b = append(b, tb)

        }
        ans, s := solution(n, m, a, b)
        fmt.Println(ans)
        if s != nil {
                for _, t := range s {
                        fmt.Println(t)
                }
        }
}

Measured memory_bytes: 20232
//C++14 (Clang 3.8.0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<long long,long long> P;
const int maxn=100010;


int main(){
  int a[maxn];
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a,a+n);
  ll res=0;
  int x=-1,y=-1;
  for(int i=0;i<n;i++){
    if(a[i]!=x){
      if(x<y)res+=(ll)(y-x);
      else if(y<x) res+=(ll)y;
      x=a[i];
      y=1;
    }
    else y++;
  }
  if(x<y)res+=(ll)(y-x);
  else if(y<x) res+=(ll)y;
  cout<<res<<endl;
  return 0;
}


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

#define max(a, b) ((a > b) ? a : b)
#define min(a, b) ((a < b) ? a : b)

#define forn(n) for(int i = 0; i < n; i++)
#define fork(k, n) for(int i = k; i < n; i++)

#define pb(n) push_back(n);

typedef long long ll;
typedef double dbl;

const int MX = 1e6;
const int MOD = 1e9 + 7;
const string ALPHA = "abcdefghijklmnopqrstuvwxyz";
const double PI = 3.1415926535;


int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
	//Code here bby
  int n;
  cin>>n;
  int elems[n];
  ll sum = 0;
  int freq[MX];
  memset(freq, 0, 4 * MX);
  forn(n){
    int elem;
    cin>>elem;
    elems[i] = elem;
    freq[elem]++;
    sum += elem;
  }
  int q; cin>>q;
  forn(q){
    ll b, c;
    cin>>b>>c;
    sum += (c - b) * (freq[b]);
    freq[c] += freq[b];
    freq[b] = 0;
    cout<<sum<<endl;
  }
}


Measured memory_bytes: 7876
import java.util.*;

public class Main {
    private static final Scanner scn = new Scanner(System.in);
    
    public static void main(String[] args) {
        int n = scn.nextInt();
        double d = 100;
        for(int i = 0; i < n; i++) {
            d = Math.ceil(d * 1.05);
        }
        System.out.println((int)d * 1000);
    }
}

Measured memory_bytes: 26232
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S,class T>ostream&operator<<(ostream&os,map<S,T>d){bool a=1;for(auto v:d){os<<(a?"":" ")<<v;a=0;}return os;};
template<class S>ostream&operator<<(ostream&os,set<S>d){bool a=1;for(auto v:d){os<<(a?"":" ")<<v;a=0;}return os;};
template<class S>auto&operator<<(ostream&os,vector<S>d){bool a=1;for(auto v:d){os<<(a?"":" ")<<v;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m=0;
    cin>>n;
    map<string,ll> mp;
    rep(i,n){
        string s;
        cin>>s;
        mp[s]++;
        chmax(m,mp[s]);
    }
    vs v;
    for(auto&p:mp)if(p.sc==m)v.push_back(p.fs);
    sort(all(v));
    for(auto&p:v)puta(p);
    return 0;
}

Measured memory_bytes: 25584
n, T = [int(n) for n in input().split()]

t = [int(n) for n in input().split()]

shower_time = 0

for i in range(1, n):
    delta = t[i] - t[i-1] 
    if delta <= T:
        shower_time += delta
    else:
        shower_time += T

shower_time += T

print(shower_time) 

Measured memory_bytes: 25172
def impossible(taro_cards, hanako_cards, average):
    if (sum(taro_cards) + sum(hanako_cards)) % 2 == 1:
        return True
    elif sum(taro_cards) + max(taro_cards) - min(hanako_cards) < average:
        return True
    elif sum(hanako_cards) + max(hanako_cards) - min(taro_cards) < average:
        return True
    else:
        return False


while True:
    n_taro, n_hanako = map(int, input().split())
    if n_taro == 0 and n_hanako == 0:
        break

    taro_cards = []
    hanako_cards = []
    change_pairs = []

    for _ in range(n_taro):
        taro_cards.append(int(input()))
    for _ in range(n_hanako):
        hanako_cards.append(int(input()))

    average = (sum(taro_cards) + sum(hanako_cards)) // 2

    if impossible(taro_cards, hanako_cards, average):
        print(-1)
    else:
        # record pairs of cards to be changed
        for i in range(len(taro_cards)):
            for j in range(len(hanako_cards)):
                if sum(taro_cards[:i]) + sum(taro_cards[i+1:]) + hanako_cards[j] == average:
                    change_pairs.append((taro_cards[i], hanako_cards[j]))
                    # print("{0} {1}".format(taro_cards[i], hanako_cards[j]))

        # print the pair of cards to be changed
        if change_pairs == []:
            print(-1)
        else:
            pairs_leastsum = change_pairs[0]
            for i in range(1, len(change_pairs)):
                if sum(change_pairs[i]) <= sum(pairs_leastsum):
                    pairs_leastsum = change_pairs[i]
            print(*pairs_leastsum)

Measured memory_bytes: 7272
n = int(input())
da = list(map(int,input().split()))
da.append(0)
da = [0] + da
su = [0 for i in range(n+2)]
for i in range(0, n+1):
    su[i+1] = su[i] + abs(da[i] - da[i+1])
for i in range(1,n+1):
    print(su[i-1] + su[-1] - su[i+1] + abs(da[i+1]-da[i-1]))

Measured memory_bytes: 14048
#include<iostream>
using namespace std;
int calc_gcd(int a,int b){
  int x=a,y=b,z;
  if(x<y){
    z=x;
    x=y;
    y=z;
  }
  while(y>0){
    z=x%y;
    x=y;
    y=z;
  }
  return x;
}
int main(){
  int a,b;
  cin>>a>>b;
  cout<<calc_gcd(a,b)<<endl;
  return 0;
}

Measured memory_bytes: 1160
def merge_and_count_rec(A, W, l, r):
    if l+1 >= r:
        return 0
    m = (l+r)//2
    cnt  = merge_and_count_rec(A, W, l, m)
    cnt += merge_and_count_rec(A, W, m, r)
    i,j,k = l,m,l
    while i<m and j<r:
        if A[i]<=A[j]:
            W[k] = A[i]
            i+=1
        else:
            W[k] = A[j]
            j+=1
            cnt += m-i
        k+=1
    if i<m:
        W[k:r] = A[i:m]
    if j<r:
        W[k:r] = A[j:r]
    A[l:r] = W[l:r]
    return cnt

N = int(input())
A = tuple(list(map(int,input().split())) for _ in range(3))
O = []
ok = True
flip = [0,0]
for i in range(N):
    ok &= (A[1][i] % 3) == 2
    ok &= sorted((A[0][i], A[1][i], A[2][i]))==[A[1][i]-1, A[1][i], A[1][i]+1]
    dist = abs(A[1][i]//3 - i)
    ok &= (dist % 2) == 0
    order = [A[0][i], A[1][i], A[2][i]] == [A[1][i]-1, A[1][i], A[1][i]+1]
    if ((dist//2)%2 == 0) != order:
        flip[i%2] += 1

B = A[1][0::2]
hb = merge_and_count_rec(B, A[0], 0, len(B))
C = A[1][1::2]
hc = merge_and_count_rec(C, A[0], 0, len(C))

ok &= (hb % 2) == (flip[1]%2)
ok &= (hc % 2) == (flip[0]%2)
print("Yes" if ok else "No")


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

int main()
{
  long N;
  long ans = 0;

  cin >> N;

  for (int i = 1; i <= N; i++)
  {
    if (i % 3 != 0 & i % 5 != 0)
    {
      ans += i;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <regex>
typedef long long ll;
using namespace std;

int main(void) {
    string S;cin>>S;
    ll N = S.size();
    ll result = 0;
    ll dp[N+1];
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        char c = S[i - 1];
        dp[i] = (c == 'B') ? dp[i - 1] + 1: dp[i - 1];
    }
    for (int i = 1; i <= N; i++) {
        if (S[i - 1] == 'W') result += dp[i];
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 2172
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
using namespace std;
typedef long long ll;
int main(){
   #ifndef ONLINE_JUDGE 
      FILE_READ_IN 
      FILE_READ_OUT 
   #endif
    string s; cin>>s;
    deque<char> st;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='B'&&!st.empty())
        {
            st.pop_back();
        }
        else if(s[i]!='B')
            st.push_back(s[i]);
    }

    while(!st.empty())
    {
        cout<<st.front();
        st.pop_front();
    }
   return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <algorithm>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;
 
int main() {

    string s;
    cin >> s;

    sort(all(s));
    if(s[0]==s[1]&&s[2]==s[3]&&s[0]!=s[2])  cout<<"Yes"<<endl;
    else    cout<<"No"<<endl;

 return 0;
}

Measured memory_bytes: 256
n = int(input())
a = [0]+list(map(int,input().split()))
N = [i for i in range(1,n+1)]
N.reverse()
ans = [0]*(n+1)
b = []

for i in N:
  if i*2 > n:
    if a[i] == 1:
      ans[i] = 1
  else:
    if a[i] == 1:
      if sum(ans[i::i])%2 == 0:
        ans[i] = 1
    else:
      if sum(ans[i::i])%2 == 1:
        ans[i] = 1
        
for i in range(1,n+1):
  if ans[i] == 1:
    b.append(i)

print(len(b))
print(*b)

Measured memory_bytes: 21676
#include<cstdio>
#include <iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pr;

int N;
int a[100010];

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++) 
		cin >> a[i+1];

	int next_button = a[1];
	int ans = 0;
	for (int i = 0; i < N; i++) {
		ans++;
		if (next_button == 2) 
			break;
		next_button = a[next_button];
	}
	if (next_button == 2) 
		cout << ans << endl;
	else
		cout << -1 << endl;
	return	0;
}

Measured memory_bytes: 640
from collections import deque


def isPalindrome(s):
    ''' s: string が回文か判定する. 回文 -> True, 回文でない -> False.
    '''
    L = len(s)
    return all(s[i] == s[L - 1 - i] for i in range(L // 2))


N = int(input())
S = []
for _ in range(N):
    s, c = input().split()
    S.append((s, int(c)))

path = [dict() for _ in range(2)]  # 余り文字列へ到達するコスト, path[0]:左側余り, path[1]: 右側余り
q = deque()
S.sort(key=lambda x: x[1])  # コストの小さい順にソートしておくと速くなる.
# 初期処理. Siを左側余り文字列と見做してキューに入れていく.
for s, c in S:
    if s not in path[0] or path[0][s] > c:
        path[0][s] = c
        q.append((0, s, c))

INF = 10 ** 15
ans = INF
while q:
    side, s0, c0 = q.popleft()

    if isPalindrome(s0):  # 余り文字列自体が回文のとき
        ans = min(ans, c0)
    else:  # 余り文字列が回文でないとき, 他の文字列を追加する
        for s1, c1 in S:
            if side == 0:
                l, r = s0, s1
            else:
                l, r = s1, s0

            L = len(l)
            R = len(r)
            isCandidate = False  # s1が追加可能な文字列かどうかを示すフラグ
            if L > R:
                if all(l[i] == r[-1 - i] for i in range(R)):
                    ns = l[R:]
                    nc = c0 + c1
                    nside = 0
                    isCandidate |= True
            elif L < R:
                if all(l[i] == r[-1 - i] for i in range(L)):
                    ns = r[:-L]
                    nc = c0 + c1
                    nside = 1
                    isCandidate |= True
            else:
                if all(l[i] == r[-1 - i] for i in range(L)):
                    ns = ''
                    nc = c0 + c1
                    nside = 0
                    isCandidate |= True
            if isCandidate and (ns not in path[nside] or path[nside][ns] > nc):
                path[nside][ns] = nc
                q.append((nside, ns, nc))
if ans < INF:
    print(ans)
else:
    print(-1)


Measured memory_bytes: 76088
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e17;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define RFOR(i, a, b) for(ll i = (a); i > b; i--)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define RREP(i, n) for(ll i = n-1; i > -1; i--)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back
#define epb emplace_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    if(s[0] == s[s.size()-1]){
        ll cnt = s.size()-2;
        cout << (cnt%2 == 0 ? "First" : "Second") << endl;
    }
    else{
        ll cnt = s.size()-2;
        cout << (cnt%2 == 1 ? "First" : "Second") << endl;
    }
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
long long f[2001][2001][2];//f[i][j][0/1]表示排到第i大的点
//左边累计j个点,往最左/右边放的ans
int n;
struct node{
	long long w;
	int id;
}a[2001];
inline bool mycmp(node x,node y){
	return x.w>y.w;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i) a[i].id=i,scanf("%lld",&a[i].w);
	sort(a+1,a+n+1,mycmp);
	for(int i=1;i<=n;++i){
		for(int j=0;j<i;++j){
			f[i][j+1][0]=max(f[i][j+1][0],f[i-1][j][1]+a[i].w*abs(a[i].id-j-1));
			if(j) f[i][j+1][0]=max(f[i][j+1][0],f[i-1][j][0]+a[i].w*abs(a[i].id-j-1));
			f[i][j][1]=max(f[i][j][1],f[i-1][j][1]+a[i].w*abs(a[i].id-n+(i-j)-1));
			if(j) f[i][j][1]=max(f[i][j][1],f[i-1][j][0]+a[i].w*abs(a[i].id-n+i-j-1));
		}
	}
	long long ans=0;
	for(int i=n;i<=n;++i)
		for(int j=1;j<=n;++j)
			ans=max(ans,max(f[i][j][0],f[i][j][1]));
	cout<<ans;
	return 0;
}

Measured memory_bytes: 42572
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define P pair<ll,ll> 
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,a=0,b=0,c=0;cin>>n;
  bool isok=false;
  for(ll i=1;i<=3500;++i) {
    for(ll j=1;j<=3500;++j) {
      ll div=4*i*j-(i+j)*n;
      if(div<=0) continue;
      if((i*j*n)%div!=0) continue;
      ll k=(i*j*n)/div;
      if(4*i*j*k==(i*j+j*k+k*i)*n) {
        a=k,b=i,c=j;
        isok=true;
      }
      if(isok) break;
    }
    if(isok) break;
  }
  printf("%lld %lld %lld\n",a,b,c);
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
const lint MOD = pow(10, 9) + 7;


int main() {
	//解説AC
	int N;
	cin >> N;
	vector<int>A(N);
	rep(i, N) {
		cin >> A[i];
	}
	rep(i, N) {
		A[i] -= (i + 1);
	}
	sort(A);
	int b = A[N / 2];
	lint sum = 0;
	rep(i, N) {
		sum += abs(A[i] - b);
	}
	cout << sum << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main() {

  int a, b, c, x;
  scanf("%d %d %d", &a, &b, &c);
  if (a > b) {
    x = a;
    a = b;
    b = x;
  }
 
  if (b > c) {
    x = b; b = c; c = x;
  }

  if (a > b) {
    x = a; a = b; b = x;
  }
  printf("%d %d %d\n", a, b ,c);

  return 0;

}

Measured memory_bytes: 596
using System;
using System.Collections.Generic;
using System.Linq;
class Program{
    static void Main(){
        string s = Console.ReadLine();
        long n = s.Length;
        long bc = 0;
        long ans = 0;
        for (int i = 0;i < n;i++){
            bc += s[i] == 'B' ? 1 : 0;
            ans += s[i] == 'B' ? n - 1 - i : 0;
        }
        ans -= bc * (bc - 1) / 2;
        Console.WriteLine(ans);
    }
}

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

const int pyonX[] = {-1, 0, 1, 2, 2, 2, 1, 0, -1, -2, -2, -2};
const int pyonY[] = {-2, -2, -2, -1, 0, 1, 2, 2, 2, 1, 0, -1};

int main() {
  int px, py;
  while (cin >> px >> py, px) {
    int n; cin >> n;
    auto g = vector<vector<int>>(10, vector<int>(10, -1));
    g[py][px] = 0;
    while (n--) {
      int x, y; cin >> x >> y;
      auto gg = g;
      for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
          if (g[i][j]) continue;
          gg[i][j] = -1;
          for (int c = 0; c < 12; ++c) {
            int ty = i + pyonY[c];
            int tx = j + pyonX[c];
            if (0 <= ty && ty < 10 && 0 <= tx && tx < 10) {
              gg[ty][tx] = 1;
            }
          }
        }
      }
      for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 1; ++j) {
          int ty = i + y;
          int tx = j + x;
          if (0 <= ty && ty < 10 && 0 <= tx && tx < 10) {
            ++gg[ty][tx];
          }
        }
      }
      for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
          g[i][j] = (gg[i][j] > 1) - 1;
        }
      }
      // for (int i = 0; i < 10; ++i) {
      //   for (auto&& x : g[i]) cout << setw(3) << right << x; cout << endl;
      // }
      // cout << endl;
    }
    bool ans = false;
    for (int i = 0; i < 10; ++i) {
      for (int j = 0; j < 10; ++j) {
        if (!g[i][j]) ans = true;
      }
    }
    cout << ( (ans) ? "OK" : "NA" ) << endl;
  }
  return 0;
}



Measured memory_bytes: 3052
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;
int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    for(int i=1;i<10000000;i++){
        if((a*i)%b==c){
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 256