akhauriyash/Code-Regression huggingface dataset:
from collections import deque

s = deque(input())

ans = 0

while len(s) >= 2:
    if s[0] == s[-1]:
        s.popleft()
        s.pop()
    elif s[0] == "x":
        s.append("x")
        ans += 1
    elif s[-1] == "x":
        s.appendleft("x")
        ans += 1
    else:
        ans = -1
        break

print(ans)

Measured memory_bytes: 4212
N, M = map(int, input().split())

a = [0]*M
b = [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())

ship_1 = []
ship_2 = []
for i in range(M):
    if a[i] == 1:
        ship_1.append(b[i])
    if b[i] == N:
        ship_2.append(a[i])

both = set(ship_1) & set(ship_2)
if len(both) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 28148
import sys
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

# 2部グラフかどうかを判定する
# 色の初期化、0:未着色
colors = [0]*n
def dfs(v, color):
    """
    parm v: node
    param color: 1 or -1
    """
    colors[v] = color
    for to in g[v]:
        if colors[to] == color:
            return False
        
        if colors[to] == 0:
            if not dfs(to, -color):
                return False
    return True

def is_bipartite():
    return dfs(0, 1)

if is_bipartite():
    # すべての対抗で辺が張れる
    print(colors.count(-1)*colors.count(1) - m)
else:
    # すべての対抗の辺が張れる
    print((n*(n-1))//2 - m)


Measured memory_bytes: 35656
N, M = map(int, input().split())
a = []
dp = [0 for i in range(N + 2)]
dp[0] = 0
dp[1] = 1
db = [1 for j in range(N + 2)]
for i in range(M):
    ta = int(input())
    db[ta + 1] = 0
for i in range(2, N + 2):
    if db[i]:
        if dp[i - 2]:
            if dp[i - 1]:
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
            else:
                dp[i] = dp[i - 2]
        else:
            if dp[i - 1]:
                dp[i] = dp[i - 1]
            else:
                print(0)
                exit()
    else:
        dp[i] = 0
print(dp[N + 1])


Measured memory_bytes: 7832
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author KharYusuf
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CLower solver = new CLower();
        solver.solve(1, in, out);
        out.close();
    }

    static class CLower {
        public void solve(int testNumber, FastReader s, PrintWriter w) {
            int n = s.nextInt();
            int max = 0, cur = 0, prev = -1;
            for (int i = 0; i < n; i++) {
                int x = s.nextInt();
                if (x > prev) {
                    max = Math.max(max, cur);
                    cur = 0;
                    prev = x;
                } else {
                    cur++;
                    prev = x;
                }
            }
            max = Math.max(cur, max);
            w.println(max);
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {

            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {

                curChar = 0;

                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public boolean isSpaceChar(int c) {

            if (filter != null)
                return filter.isSpaceChar(c);

            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 23764
#include<stdio.h>

int main()
{
    int n;
    int i;
    scanf("%d",&n);
    int x[n+1];
    for(i=1;i<=n;i++){
        scanf("%d",&x[i]);
    }
    long sum=0;
    int ave;
    for(i=1;i<=n;i++){
        sum+=x[i];
    }
    ave=sum/n;
    long cost=0;
    long cost_prev=0;
    long cost_next=0;
    for(int i=1;i<=n;i++){
        cost+=(x[i]-ave)*(x[i]-ave);
    }
    for(int i=1;i<=n;i++){
        cost_prev+=(x[i]-ave-1)*(x[i]-ave-1);
    }
    for(int i=1;i<=n;i++){
        cost_next+=(x[i]-ave+1)*(x[i]-ave+1);
    }
    int j=1;
    int flag=0;
    if(cost>cost_prev){
        flag=1;
    }
    else if(cost>cost_next){
        flag=2;
    }
    while(flag==1){
        for(int i=1;i<=n;i++){
            cost+=(x[i]-ave-j-1)*(x[i]-ave-j-1);
        }if(cost<cost_prev){
            cost_prev=cost;
            
        }else{
            flag=0;
            cost=cost_prev;
        }
    }    
    while(flag==2){
        for(int i=1;i<=n;i++){
            cost+=(x[i]-ave+j+1)*(x[i]-ave+j+1);
        }if(cost<cost_next){
            cost_next=cost;
            
        }else{
            flag=0;
            cost=cost_next;
        }
    }
    printf("%ld\n",cost);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 18, N = (1<<16)+5, mod = 1e9+7;
ll b, n, m, a[M], fac[N] = {1}, fi[N] = {1}, dt[M][N];

ll calc (ll X, ll Y) {
	if(!Y) return 1;
	ll R = calc(X, Y/2);
	R = R * R % mod;
	if(Y&1) R = R * X % mod;
	return R;
}

ll comb (ll A, ll B) {
	if(B < 0 || A < B) return 0;
	return fac[A] * fi[B] % mod * fi[A-B] % mod;
}

void solve (ll X, ll A) {
	if(b-a[X]+1 < A) return;
	for(int i=0;i<n;i++) {
		int j = (1<<i);
		if(!(j&A)) continue;
		dt[X][A] = (dt[X][A] + dt[X+1][A-j] * comb(b-a[X]-A+j, j-1) % mod * fac[j]) % mod;
	}
}

int main()
{
	scanf("%lld%lld",&n,&m);
	b = (1<<n);
	for(int i=1;i<=b;i++) {
		fac[i] = fac[i-1] * i % mod;
		fi[i] = calc(fac[i], mod-2);
	}
	for(int i=1;i<=m;i++) {
		scanf("%lld",&a[i]);
	}
	dt[m+1][0] = 1;
	for(int i=m;i>=1;i--) {
		dt[i][0] = dt[i+1][0];
		for(int j=1;j<b;j++) {
			dt[i][j] = dt[i+1][j];
			solve(i, j);
		}
	}
	ll ans = 0;
	for(int i=0;i<b;i++) {
		ans = (ans + b * fac[b-i-1] % mod * (mod + 1 - __builtin_popcount(i)%2*2) % mod * dt[1][i] % mod) % mod;
	}
	printf("%lld\n",ans);
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

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

    char dp[3][3];
    REP(i, 3) REP(j, 3) cin >> dp[i][j];
    REP(i, 3) cout << dp[i][i];
    cout << endl;
    return 0;
}

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

int dp[100][5][5];
int mp[100]={0};
int mod=10000,n;

int dfs(int d,int ppr,int pre){
    int res=0;
    if(d==n) return 1;
    if(dp[d][ppr][pre]!=-1) return dp[d][ppr][pre];
    if(mp[d]!=0){
        int t=mp[d];
        if(ppr==pre&&t==pre) return 0;
        res +=dfs(d+1,pre,t);
    }
    else{
        for(int i=1;i<4;++i){
            if(ppr==pre&&i==pre) continue;
            res +=dfs(d+1,pre,i);
        }
    }
    res %=mod;
    dp[d][ppr][pre]=res;
    return res;
}

int main(){
    int k,a,b;
    cin>>n>>k;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<k;++i){
        cin>>a>>b;
        mp[a-1]=b;
    }
    cout<<dfs(0,4,4)%mod<<endl;
    return 0;
}

Measured memory_bytes: 3096
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

vector<int>E[1010];
vector<pair<int, int>>p;
int used[1010];
set<int>li;
int N, M;
int dfs(int now,int st) {
	int ok = 0;
	fore(x, E[now]) {
		if (!used[x]) {
			used[x] = 1;
			if(dfs(x, st))ok = 1;
		}
		if (x == st)return 1;
	}
	return ok;
}

void yatta(int st) {
	li.insert(st);
	int cnt = 0;
	fore(x, p) {
		if (li.count(x.first) && li.count(x.second))cnt++;
	}
	if (cnt != li.size())return;
	puts(li.size());
	fore(x,li)puts(x+1);
	exit(0);
}

void dfs2(int now,int st) {
	fore(x, E[now]) {
		if (!used[x]) {
			used[x] = 1;
			li.insert(x);
			dfs2(x,st);
			li.erase(x);
		}
		if (x == st)yatta(st);
	}
	return;
}


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

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		A--, B--;
		E[A].pb(B);
		p.pb({ A,B });
	}

	int rec = -1;
	for (int i = 0; i < N; i++) {
		memset(used, 0, sizeof(used));
		used[i] = 1;
		if (dfs(i, i)) {
			memset(used, 0, sizeof(used));
			dfs2(i,i);
		}
	}
	puts(-1);
	
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for(int i=0; i<(a); i++)
typedef long long ll;

int main()
{
  int n, m; cin >> n >> m;
  for (int i=0; i<m; i++){
    int a; cin >> a;
    n -= a;
  }
  cout << max(-1, n) << endl;

  return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int N;
  cin>>N;
  
  string w[110];
  for(int i=0;i<N;++i){
    cin>>w[i];
  }
  
  bool exist_same=false;
  bool not_shiritori=false;
  
  for(int i=0;i<N;++i){
    for(int j=i+1;j<N;++j){
      if(w[i]==w[j])
        exist_same=true;
    }
  }
  
  for(int i=0;i<N-1;++i){
    if(w[i][w[i].size()-1]!=w[i+1][0])
      not_shiritori=true;
  }
  
  if(exist_same || not_shiritori)
    cout<<"No"<<endl;
  else
    cout<<"Yes"<<endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
#define uni(q) unique(all(q)),q.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

int main(){
    ll n,m; cin >> n >> m;
    vl a(m);
    rep(i,m) cin >> a[i];
    reverse(all(a));
    vl dp(n+1,-1);
    if(!a.empty() && a.back()-1 == 0){
        dp[0] = 0;
        a.pop_back();
    }
    if(!a.empty() && a.back()-1 == 1){
        dp[1] = 0;
        a.pop_back();
    }
    if(dp[0] != 0) dp[0] = 1;
    if(dp[1] != 0) dp[1] = dp[0] + 1;
    rep(i,n-2){
        if(a.empty() || a.back()-1 != i+2){
            dp[i+2] = (dp[i+1] + dp[i]) % MOD;
            dp[i+2] %= MOD;
        }else{
            dp[i+2] = 0;
            a.pop_back();
        }
    }
    //rep(i,n) cout << dp[i] << " ";
    cout << dp[n-1] << endl;
}


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

string replaceAAAtoBBB(const string& str) {
  string str2(str);
  string before = "Hoshino";
  string after = "Hoshina";
  int idx = 0;

  while( (idx = str2.find(before, idx)) >= 0) {
	str2.replace(idx, before.length(), after);
  }
  return str2;
}

int main() {
  int n;
  string buf;

  cin >> n;
  cin.ignore();
  
  for(int i = 0; i < n; ++i) {
	getline(cin, buf);
	cout << replaceAAAtoBBB(buf) << endl;
  }

  return 0;
}

Measured memory_bytes: 3148
#include <iostream>
#include <iostream>

int main()
{
	int N, Y;
	scanf("%d %d", &N,&Y);

	int i, j, k;

	for (i = N; i >= 0; i--) {
		for (j = N - i; j >= 0; j--) {
			k = N - i - j;

			if (10000 * i + 5000 * j + 1000 * k == Y) {
				printf("%d %d %d", i, j, k);
				return 0;
			}
		}
	}

	printf("%d %d %d", -1, -1, -1);

}


Measured memory_bytes: 256
/* vishal shrivastava
     185023
     nit hamirpur
   */
  #include <bits/stdc++.h>
  using namespace std;
  #define minpq priority_queue <int, vector<int>, greater<int> >;
  #define maxpq  priority_queue <int>;
  #define F first
  #define S second
  #define mp make_pair
  #define pb push_back
  #define f(i,x,n) for(int i=x;i<n;i++)
  #define all(c) c.begin(),c.end()
  #define ll long long
  #define pll pair<ll,ll>
  #define pii pair<int,int>
  const int mod = 1e9+7, N = 1e5 + 10;
  int solve()
  {
     ll a;
     string s;
     cin>>a>>s;
     if(a>=3200)
        cout<<s;
     else
        cout<<"red";
  }

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


Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;

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


/******************************************************************************************/



//ユークリッド互除法
template<typename T>
T gcd(T x, T y) {

	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x % y);
	}
}

/*最小公倍数*/
template<typename T>
T lcm(T x, T y) {
	T tmp = gcd(x, y);

	return x * y / tmp;
}


int main() {

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


	int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < n-2; i++)
    {
        if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C'){
            cnt++;
        }
        /* code */
    }
    
    cout << cnt << endl;

	

	return 0;
}



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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef vector<pll> vpll;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back

inline void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

inline void OUT(void){
  cout << "\n";
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cout << VEC[i] << " ";
  }
  cout << "\n";
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i, MAT.size()){
    REP(j, MAT[i].size()){
      cout << MAT[i][j] << " ";
    }
    cout << "\n";
  }
};

template <typename CLASS1, typename CLASS2>
class HOGE{
  public:
    CLASS1 key;
    CLASS2 value;
    HOGE(void){
      return;
    };
    HOGE(CLASS1 key, CLASS2 value){
      this->key = key;
      this->value = value;
    };
    ~HOGE(void){
      return;
    };

    void print(void){
      cout << "key : " << key << ", value : " << value << "\n";
      return;
    };
    
    bool operator==(const HOGE &obj){
      return (this->value == obj.value);
    };
    bool operator<(const HOGE &obj){
      return (this->value < obj.value);
    };
    bool operator>(const HOGE &obj){
      return (this->value > obj.value);
    };
};

template <typename CLASS1, typename CLASS2>
bool operator==(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
  return hoge1.value == hoge2.value;
};

template <typename CLASS1, typename CLASS2>
bool operator<(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
  return hoge1.value < hoge2.value;
};

template <typename CLASS1, typename CLASS2>
bool operator>(const HOGE<CLASS1, CLASS2> &hoge1, const HOGE<CLASS1, CLASS2> &hoge2){
  return hoge1.value > hoge2.value;
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  ll N;
  IN(N);
  ll ans = 0;
  REP(i,N){
    ans += i;
  }
  OUT(ans);

  return 0;
}

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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; }

int main(void){
    int N; cin >> N;
    VI X(N); REP(i,N) cin >> X[i];
    SORT(X);

    int ans = INT_INF;
    FOR(i,X[0],X[N-1]+1){
        int tmp = 0;
        REP(j,N) tmp += (i - X[j])*(i - X[j]);
        chmin(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int n, q;
  int x;
  int C = 0;

  std::scanf("%d", &n);
  std::vector<int> S;
  S.reserve(n);
  while (--n > -1) {
    std::scanf("%d", &x);
    S.push_back(x);
  }
  std::scanf("%d", &q);
  std::vector<int> T;
  T.reserve(q);
  while (--q > -1) {
    std::scanf("%d", &x);
    T.push_back(x);
  }

  for (int i = 0; i < T.size(); ++i) {
    for (int j = 0; j < S.size(); ++j) {
      if (S[j] == T[i]) {
        ++C;
        break;
      }
    }
  }

  std::printf("%d\n", C);

  return 0;
}



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

int main() {
    int a, b; cin >> a >> b;
    if(a - 2*b <= 0) cout << 0 << endl;
    else cout << a - 2*b << endl;

    return 0;
}

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

int main() {
    int N, C;
    cin >> N >> C;
    using P = pair<int, int>;
    using PI = pair<P, int>;
    priority_queue<PI, vector<PI>, greater<PI>> pq;
    rep(i, 0, N) {
        int s, t, c;
        cin >> s >> t >> c;
        s = 2 * s;
        t = 2 * t + 1;
        pq.push(PI(P(s, c), 0));
        pq.push(PI(P(t, c), 1));
    }
    int ans = 0;
    int cnt = 0;
    vector<int> used(C + 1);
    while(!pq.empty()) {
        PI t = pq.top(); pq.pop();
        int ch = t.first.second;
        int type = t.second;
        if(type == 0) {
            if(used[ch] == 0) cnt++;
            used[ch]++;
        } else {
            used[ch]--;
            if(used[ch] == 0) cnt--;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4852
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;

#define rep(i,N) for(ll i=0;i<(ll)N;++i)

ll GCD(ll x, ll y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}

#include <iostream>

int main()
{
    ll A,B,X;

    cin >> X;

    for (A = -119; A <= 119; ++A) {
        for (B = -119; B <= A; ++B) {
            if (A * A * A * A * A - B * B * B * B * B == X) { cout << A << " " << B << endl; goto xyz; }
        }
    }
xyz:;
}

Measured memory_bytes: 3584
n = gets.to_i
if n==1000000000000000000
  x1=0
  y1=0
  x2=0
  y2=1000000000
  x3=1000000000
  y3=0
  puts "#{x1} #{y1} #{x2} #{y2} #{x3} #{y3} "
  exit 0
end
xx=(10**9)
x1=0
y1=0
m=xx - (n % xx)
d= n/xx
x2=m
y2=d+1
x3=xx
y3=1
p
puts "#{x1} #{y1} #{x2} #{y2} #{x3} #{y3} "


Measured memory_bytes: 1788
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")



#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// #define Find order_of_key
// #define at find_by_order
#define x first
#define y second
#define ll long long
#define lll __int128
#define ull unsigned long long
#define ulll unsigned __int128
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define gu getchar_unlocked()
#define pu putchar_unlocked()
#define all(x) x.begin(),x.end()
#define endl '\n'

const int mx=100010;
int arr[mx];
int n;

int main()
{
	fast;
	cin>>n;
	int ma=0;
	int s=1;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		if(arr[i]>arr[i-1]){
			ma=max(ma,s);
			s=1;
		}else{
			s++;
		}
	}
	ma=max(ma,s);
	cout<<ma-1<<endl;
	return 0;
}

Measured memory_bytes: 3976
import java.util.*;

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

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int count = map.getOrDefault(a, 0);
            map.put(a, ++count);
        }

        List<Integer> candidate = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            if (e.getValue() >=4) {
                candidate.add(e.getKey());
                candidate.add(e.getKey());
            } else if (e.getValue() >= 2) {
                candidate.add(e.getKey());
            }
        }

        candidate.sort(Collections.reverseOrder());
        if (candidate.size() < 2) {
            System.out.println(0);
        } else {
            System.out.println((long)candidate.get(0) * candidate.get(1));
        }
    }
}


Measured memory_bytes: 63124
#include <stdio.h>
#define N 100000

void swap(int *x, int *y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

int partition(int a[], int p, int r){
    int i = p-1;        // p = 0
    int j;              
    int key = a[r];     // r = n-1

    for (j = p; j < r; j++) {
        if(key >= a[j]) {
            i++;
            swap(&a[j], &a[i]);
        }
    }
    swap(&a[i+1], &a[r]);
    return i+1;
    

}



int main() {
    int n, a[N], i;
    scanf("%d", &n);

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

    int p = 0;
    int r = n-1;
    int key = partition(a, p, r);

    for (i = 0; i < n-1; i++) {
        if(key == i) printf("[%d] ", a[i]);
        else printf("%d ", a[i]);
    }
    printf("%d\n", a[n-1]);
    
    return 0;
}

Measured memory_bytes: 988
//マージソート
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void merge(int *,int ,int ,int);
void mergeSort(int *,int, int);

int count=0;
int main() {
  int i,j;
  int *S;
  int n;
  int left=0,mid,right;

  scanf("%d",&n);
  S = (int *)malloc((n+1) * sizeof(int));
  for(i=0;i<n;i++) scanf("%d",&S[i]);

  right = n;
  mergeSort(S,left,right);

  for(i=0;i<n-1;i++) {
    printf("%d ",S[i]);
  }
  printf("%d\n%d\n",S[n-1],count);
  
  return 0;
}

void merge(int *A,int left,int mid,int right) {
  int n1,n2;
  int *L,*R;
  int i,j;
  int k;
  n1 = mid-left;
  n2 = right - mid;
  L = (int *)malloc((n1+1) * sizeof(int));
  R = (int *)malloc((n2+1) * sizeof(int));
  for(i=0;i<n1;i++) {
    L[i] = A[left + i];
  }
  for(i=0;i<n2;i++) {
    R[i] = A[mid+i];
  }
  L[n1] = INT_MAX;
  R[n2] = INT_MAX;
  i=j=0;
  for(k=left;k<right;k++) {
    count++;
    if(L[i] <= R[j]) {
      A[k] = L[i];
      i++;
    }
    else {
      A[k] = R[j];
      j++;
    }
  }
}

void mergeSort(int *A,int left,int right) {
  int mid;
  if(left+1 < right) {
    mid = (left + right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
    
  }
}



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

int main()
{
	int H, W;
	vector<string> S;
	cin >> H >> W;
	S.resize(H);
	for (int i = 0; i < H; i++)
		cin >> S[i];
	int dh[8] = { 0,1,1,1,0,-1,-1,-1 };
	int dw[8] = { 1,1,0,-1,-1,-1,0,1 };
	for(int h=0;h<H;h++)
		for (int w = 0; w < W; w++)
		{
			int a = 0;
			if (S[h][w] == '.')
			{
				for (int i = 0; i < 8; i++)
				{
					if ((h+dh[i]) >=0 && (h + dh[i]) < H && (w+dw[i])>=0 && (w+dw[i] < W) &&  S[h + dh[i]][w + dw[i]] == '#')
						a++;
				}
				S[h][w] = '0'+a;
			}

		}

	for (int i = 0; i < H; i++)
		cout << S[i] << endl;
	return 0;
}

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

int main() {

	const int p = 3;
	vector<int> c(p);
	for (int i = 0; i < p; i++) {
		cin >> c[i];
	}
	int k; cin >> k;
	sort(c.rbegin(), c.rend());
	while (k--) {
		c[0] *= 2;
	}
	cout << c[0] + c[1] + c[2] << endl;
	return 0;
}

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

using namespace std;

int N, A, B, C;
std::vector<int> l;
int dfs(int cur, int a, int b, int c) {
  if (cur == N) {
    if (min(min(a,b),c) > 0) return abs(a-A) + abs(b-B) + abs(c-C) -30;
    else return 100000;

  }
  int ret0 = dfs(cur+1, a, b, c);
  int ret1 = dfs(cur+1, a+l[cur], b, c) + 10;
  int ret2 = dfs(cur+1, a, b+l[cur], c) + 10;
  int ret3 = dfs(cur+1, a, b, c+l[cur]) + 10;
  return min(min(min(ret0,ret1),ret2),ret3);
}

int main(int argc, char const *argv[]) {

  std::cin >> N >> A >> B >> C;
  for (int i=0; i<N; i++) {
    int z; std::cin >> z;
    l.push_back(z);
  }
  int ans = dfs(0,0,0,0);
  std::cout << ans << '\n';

  return 0;
}


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


int main() {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;
  int price = 0;
  int diff = abs(X - Y);
  if(2 * C < A + B) {
    price += min(X, Y) * 2 * C;
    if(X > Y) {
      if(A >= 2 * C) price += diff * 2 * C;
      else price += diff * A;
    }
    if(X < Y) {
      if(B >= 2 * C) price += diff * 2 * C;
      else price += diff * B;
    }
  } else {
    price = A * X + B * Y;
  }

  cout << price << "\n";
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
  int a[201] = {};
  int i;
  int n, l;
  int min, minabs = 10000, taste, s = 0;

  scanf("%d", &n);
  scanf("%d", &l);
  
  for (i = 1; i <= n; i++) {
    a[i] = l + i - 1;
  }

  for (i = 1; i <= n; i++) {
    if (a[i] < 0) {
      taste = -a[i];
    } else {
      taste = a[i];
    }
    if (taste < minabs) {
      min = a[i];
      minabs = taste;
    }
    s += a[i];
  }

  printf("%d\n", s - min);
  
  return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(void){
	int n,i,r=1;
	char s[100];
	scanf("%d%s",&n,s);
	if(n%2){
		r=0;
	}
	else{
		for(i=0;i<n/2;i++){
			r*=s[i]==s[n/2+i];
		}
	}
	printf(r?"Yes":"No");
	return 0;
}

Measured memory_bytes: 1732
n = int(input())
P = list(map(int,input().split()))
cnt=0
for i in range(1,n-1):
  if P[i]<P[i+1] and P[i]>P[i-1]:
    cnt += 1
  elif P[i]>P[i+1] and P[i]<P[i-1]:
    cnt += 1

print(cnt)

Measured memory_bytes: 3060
#include <stdio.h>

int main (void)
{
	int a,b,c;
	
	scanf("%d",&a);
	scanf("%d",&b);
	scanf("%d",&c);
	
	if(c>=a && c<=b){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	
	return 0;
}


Measured memory_bytes: 128
#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<cmath>
    #include<algorithm>
     
    using namespace std;
     
    int main(){
    	int a,b;
    	scanf("%d",&a);
putchar('\n');
        scanf("%d",&b);
        printf("%d",2*b-a);
        return 0;
    }

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <cctype>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 1001001001001001001;  // > 10^18
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    int n; cin >>n;
    vector<priority_queue<char, vector<char>, greater<char> > > s(n, priority_queue<char, vector<char>, greater<char> >());

    for (int i = 0; i < n; i++) {
        string this_s; cin >> this_s;
        for (int j = 0; j < this_s.length(); j++) {
            s[i].push(this_s[j]);
        }
    }

    string ans = "";
    for (char c = 'a'; c <= 'z'; c++) {
        int minc = INF;
        for (int i = 0; i < n; i++) {
            int count = 0;
            while (!s[i].empty()) {
                char t = s[i].top();
                if (t == c) {
                    s[i].pop();
                    count++;
                } else {
                    break;
                } 
            }
            minc = min(minc, count);
        }
        for (int t = 0; t < minc; t++) {
            ans += c;
        }
    }
    
    cout << ans << endl;
    return 0;
}




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

using namespace std;

typedef long long ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    unordered_map<ll,ll> m;
    unordered_map<ll,ll> cnt;

    ll n;
    cin >> n;
    vector<ll> v(n);

    for(int i = 0 ; i < n ; ++i){
        cin >> v[i];
        m[v[i]] += 1;
    }
    ll sum = 0;
    for(auto it = m.begin(); it != m.end(); ++it){
        sum += (it->second) * (it->second - 1) / 2;
        cnt[it->first] = 0;
    }
    for(auto it = cnt.begin(); it != cnt.end(); ++it){
        ll a = m[it->first];
        it->second = sum - (a * (a - 1) / 2) +  ((a-1)*(a-2) / 2);
    }
    for(int i = 0 ; i < n; ++i){
        cout << cnt[v[i]] << endl;
    }



    return 0;
}

Measured memory_bytes: 17096
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
using namespace std;
 
int main(){
    string s,t; cin >> s >> t;
    int ans=0;
    rep(i,3){
        if(s[i]==t[i]) ans++;
    }
    cout << ans << endl;
return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
//#include<bits/stdc++.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<sstream>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
#include<limits.h>
#define inf 0x3fffffff
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
using namespace std;
int a[1000][1000];
int w,h;
int x,y;
int t;
int n;
void cmd(int x,int y,int pos)
{
    if(pos==1)
    {
        for(int i=1;i<=h;i++)
        {
            for(int j=1;j<=x;j++)
            {
                a[i][j]=1;
            }
        }
    }
    else if(pos==2)
    {
        for(int i=1;i<=h;i++)
        {
            for(int j=x+1;j<=w;j++)
            {
                a[i][j]=1;
            }
        }
    }
    else if(pos==3)
    {
        for(int i=1;i<=y;i++)
        {
            for(int j=1;j<=w;j++)
            {
                a[i][j]=1;
            }
        }
    }
    else
    {
        for(int i=y+1;i<=h;i++)
        {
            for(int j=1;j<=w;j++)
            {
                a[i][j]=1;
            }
        }
    }
}
int main()
{
    cin>>w>>h>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>x>>y>>t;
        cmd(x,y,t);
    }
    int sum=0;
    for(int i=1; i<=h; i++)
    {
        for(int j=1; j<=w; j++)
        {
            if(a[i][j]==0)
            {
               sum++;
            }
        }
    //    cout<<endl;
    }
    cout<<sum<<endl;
    return 0;
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

typedef long long ll;
typedef pair<int, int> Pi;

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
    int X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;

    vector<int> P(A), Q(B), R(C);
    rep(i, A) cin >> P[i];
    rep(i, B) cin >> Q[i];
    rep(i, C) cin >> R[i];

    sort(P.begin(), P.end(), greater<int>());
    sort(Q.begin(), Q.end(), greater<int>());
    sort(R.begin(), R.end(), greater<int>());

    vector<Pi> v;
    rep(i, X) v.push_back(Pi(P[i], 0));
    rep(i, Y) v.push_back(Pi(Q[i], 1));

    sort(v.begin(), v.end());

    ll ans = 0;
    for (auto &i : v) ans += i.first;

    int idx = 0;
    for (auto &i : v) {
        if (idx < C && i.first < R[idx]) {
            ans -= i.first;
            ans += R[idx];
            idx++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3572
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Segment_Tree{
	private:
	int n;
	vi date;
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vi(2*n-1);
	}
	void Update(int k,int x){
		k+=n-1;
		date[k]+=x;
		while(k>0){
			k=(k-1)/2;
			date[k]=date[k*2+1]+date[k*2+2];
		}
	}
	int Query(int a,int b){
		a+=n-1;b+=n-1;
		int m=0;
		while(a<b){
			if(a%2==0) m+=date[a++];
			if(b%2==0) m+=date[--b];
			a/=2;b/=2;
		}
		return m;
	}
	int Open(int k){return date[k+n-1];}
};

int n,q;
vi a,c;
vip b;

int main(){
	cin>>n>>q;
	a=vi(n);
	c=vi(q);
	b=vip(q);
	for(auto &i:a)cin>>i;
	for(int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		l--,r--;
		b[i]={{r,l},i};
	}
	sort(b.begin(),b.end());
	int I=0;
	Segment_Tree st(n);
	vi d(n,-1);
	for(int i=0;i<n;i++){
		int x=a[i]-1;
		if(d[x]>=0) st.Update(d[x],-1);
		d[x]=i;
		st.Update(i,1);
		while(I<q&&b[I].first.first==i){
			c[b[I].second]=st.Query(b[I].first.second,n);
			I++;
		}
	}
	for(auto i:c)cout<<i<<endl;
}

Measured memory_bytes: 19576
#include <stdio.h>
#include <iostream>
using namespace std;
#define N_MAX 100
#define W_MAX 10000
int DP[N_MAX + 1][W_MAX + 1];

int main(void){
    int N, W;
    scanf("%d", &N);
    scanf("%d", &W);

    int v[N_MAX];
    int w[N_MAX];
    for(int i = 1; i <= N; i++){
        scanf("%d", &v[i]);
        scanf("%d", &w[i]);
    }

    for(int i = 0; i <= W; i++){
        DP[0][i] = 0;
    }

    for(int j = 0; j <= N; j++){
        DP[j][0] = 0;
    }

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= W; j++){
            if(j - w[i] >= 0){
                DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - w[i]] + v[i]);
            }else{
                DP[i][j] = DP[i - 1][j];
            }
        }
    }

    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= W; j++){
            //printf("DP[%d][%d] = %d\n", i, j, DP[i][j]);
        }
    }


    printf("%d\n", DP[N][W]);
    
}



Measured memory_bytes: 7144
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (long long i = (a); i <= (b); i++)
#define FORD(i,a,b) for (long long i = (a); i >= (b); i--)
#define REP(i,a) FOR(i,0,(long long)(a)-1)
#define reset(a,b) memset(a,b,sizeof(a))
#define all(x) x.begin(), x.end()
#define uni(x) x.erase(unique(all(x)), x.end());
#define BUG(x) cout << #x << " = " << x << endl
#define BUGP(x) cout << #x << " = " << x._1 << ", " << x._2 << endl
#define PR(x,a,b) {cout << #x << " = "; FOR (_,a,b) cout << x[_] << ' '; cout << endl;}
#define CON(x) {cout << #x << " = "; for(auto _i:x) cout << _i << ' '; cout << endl;}
#define mod 1000000007
#define pi acos(-1)
#define eps 1e-8
#define pb push_back
#define sqr(x) (x) * (x)
#define _1 first
#define _2 second

int n, dp[100500];
vector<int> v;

int main() {
  ios::sync_with_stdio(false);
  for (int i = 1; i <= 100000; i *= 6) v.pb(i);
  for (int i = 9; i <= 100000; i *= 9) v.pb(i);
  cin >> n;
  reset(dp, 55);
  dp[0] = 0;
  FOR (i, 1, n) for (auto j: v) if (i - j >= 0) dp[i] = min(dp[i], dp[i - j] + 1);
  cout << dp[n];
}


Measured memory_bytes: 768
n,m = map(int,input().split())
x = []
y = []
for _ in range(n):
    a,b = map(int,input().split())
    x.append([a,b])
for _ in range(m):
    c,d = map(int,input().split())
    y.append([c,d])
for i in range(n):
    t = 10**8*3
    ans = 0
    for j in range(m):
        if t > abs(y[j][0]-x[i][0])+abs(y[j][1]-x[i][1]):
            ans = j+1
            t = abs(y[j][0]-x[i][0])+abs(y[j][1]-x[i][1])
    print(ans)

Measured memory_bytes: 3064
N = int(input())
*a,= map(int, input().split())
count,result={},{}

for i in range(N):
  count[a[i]]=0
  result[a[i]]=0
  
def ncn(n):
  return n*(n-1)//2

for i in range(N):
  count[a[i]]+=1

total=0
for key in count.keys():
  kc = count[key]
  result[key]=ncn(kc)
  total += result[key]
  
def without(k):
  return total-count[a[k]] + 1

for k in range(N):
  print(without(k))



Measured memory_bytes: 30592
#include<stdio.h>
int main()
{
  int n=0,y=0,sen=0,gosen=0,man=0,flag=0;
  scanf("%d %d",&n,&y);
  for(sen=0;sen<=n;sen++){
    for(gosen=0;gosen<=n;gosen++){
      man=n-(sen+gosen);
      if(sen*1000+gosen*5000+man*10000==y&&
         sen+gosen+man==n&&man>=0){
        flag=1;break;}
    }
    if(sen*1000+gosen*5000+man*10000==y&&
         sen+gosen+man==n&&man>=0){
        flag=1;break;}
  }
  if(flag==1) printf("%d %d %d",man,gosen,sen);
  else printf("-1 -1 -1");
    return 0;
  }


Measured memory_bytes: 1732
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  for (ll i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  
  ll min = 1e9, r;
  for (ll i = 0; i < n-1; i++) {
    long double d = abs(a[n-1]/2.0 - a[i]);
    if (d < min) {
      min = d;
      r = a[i];
    }
  }
  cout << a[n-1] << ' ' << r << endl;
}

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

int main()
{
  int a,b;
  int ans=0;
  int c;
  int d;
  cin>>a>>b;
  for(int i=0; i<a; i++){
    cin>>c;
    ans+=c;
    d=i+1;
    if(ans>b){
      break;
    }
  }
  if(ans<= b) cout << d+1 <<endl;
  else cout << d <<endl;
}

Measured memory_bytes: 256
import copy

def bit_list(x: int, n: int) -> list:
    '''
    xのn乗のbit配列を返す
    '''
    ans = []
    for i in range(x ** n):
        num = i
        j = 0
        table = [0 for _ in range(n)]
        while num:
            table[j] = num % x
            num = num // x
            j += 1

        ans.append(table)

    return ans

H, W, K = map(int, input().split())
M = [list(input()) for _ in range(H)]

ans = 0
bits = bit_list(2, H + W)

for bit in bits:
    tmp_M = copy.deepcopy(M)
    for i in range(H + W):
        if i < H and bit[i] == 1:
            for j in range(W):
                 tmp_M[i][j] = "R"
        if i >= H and bit[i] == 1:
            for j in range(H):
                 tmp_M[j][i - H] = "R"

    count = 0
    for i in range(H):
        for j in range(W):
            if tmp_M[i][j] == '#':
                count += 1

    if count == K:
        ans += 1

print(ans)

Measured memory_bytes: 9860
import java.util.Scanner;

public class Main {

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

		int a=scan.nextInt();
		int b=scan.nextInt();
		int h=scan.nextInt();

		int kotae=(a+b)*h/2;

		System.out.println(kotae);

	}

}


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

int main(){
  int A,B,K;
  cin>>K>>A>>B;
  for(int i=A;i<=B;i++){
    if(i%K==0){
      cout<<"OK"<<endl;
      return 0;
    }
  }
  cout<<"NG"<<endl;
  return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#define debug(x) cerr << #x << ':' << (x) << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }


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

	int n;
	cin >> n;
	ll l = 0, r = n;
	vector<int> a(n + 1);
	cout << "? ";
	for (int i = 1; i <= n; i++) cout << i << ' ';
	cout << endl;
	string s;
	cin >> s;
	if (s == "Red") a[0] = 1;
	else a[0] = -1;
	a[n] = -a[0];
	int pre = 0;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		cout << "? ";
		for (int i = 1; i <= n; i++) {
			if (i <= mid) cout << i + n << ' ';
			else cout << i << ' ';
		}
		cout << endl;
		string t;
		cin >> t;
		if (t == "Red") a[mid] = 1;
		else a[mid] = -1;
		if (pre < mid && a[pre] == a[mid] || pre > mid && a[pre] != a[mid]) l = mid;
		else r = mid;
		pre = mid;
	}
	vector<int> vec;
	vector<bool> use(2 * n);
	rep(i, l) {
		use[n + i] = true;
		vec.pb(n + i);
	}
	for (int i = l + 1; i < n; i++) {
		use[i] = true;
		vec.pb(i);
	}
	vector<int> ans(2 * n);
	vector<int> red, blue;
	rep(i, 2 * n) {
		if (!use[i]) {
			cout << "? ";
			for (int x : vec) cout << x + 1 << ' ';
			cout << i + 1 << endl;
			string t;
			cin >> t;
			if (t == "Red") {
				ans[i] = 1;
				red.pb(i);
			}
			else {
				ans[i] = -1;
				blue.pb(i);
			}
		}
	}
	vector<int> check;
	rep(i, (n - 1) / 2) {
		check.pb(red[i]);
		check.pb(blue[i]);
	}
	rep(i, 2 * n) {
		if (use[i]) {
			cout << "? ";
			for (int x : check) cout << x + 1 << ' ';
			cout << i + 1 << endl;
			string t;
			cin >> t;
			if (t == "Red") ans[i] = 1;
			else ans[i] = -1;
		}
	}
	cout << "! ";
	rep(i, 2 * n) cout << (ans[i] == 1 ? 'R' : 'B');
	cout << endl;
}

Measured memory_bytes: 3820