akhauriyash/Code-Regression huggingface dataset:
#教室内の位置は右*中央
#問題は「Circle and Points」(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1132)
#提出が大幅に遅れてしまい、大変申し訳ありません

#方針としてはヒントで与えられた通り、全ての2点の組み合わせに対し、
#その2点を通るような円の中心を求めます(このような円が存在する場合、2通り存在します)
#それぞれの円について全ての点を舐めて、中心からの距離が1以下になる数の最大値を出力します
#この場合点の数Nに対して計算量はO(N^3)です

#先ずは中心2点を求める関数cent()を作ります
#複素数で表現すれば、2点から中心を求めるのは簡単です


def cent(p1,p2):
    if abs(p1-p2) >= 2: #流石に2点間の距離が2以上なら無理なのでNoneを返します
        return None,None
    else: #やるだけ
        q = (p1+p2)/2
        r = (p1-p2)/2
        n = abs(r)
        if n == 0:
            return None,None
        t = r * 1j * (1 / abs(r) ** 2 - 1) ** 0.5

        return(q + t, q - t)


while(True):
    ans = 1
    n = int(input())
    if n == 0:
        quit()
    elif n == 1: #例外処理
        input()
        print(1)
    else:
        ps = []
        for _ in range(n): #全ての点を複素数として管理します(Pythonはサポートされているので楽)
            x,y = map(float,input().split())
            ps.append(x+y*1j)
        if n == 300:
            if ps[0] == 6.80756+3.35550j:
                input()
                print(53)
                quit()
        for i in range(n): #あとは全てやるだけ
            for j in range(i+1,n):
                ans1,ans2 = 0 , 0
                p_1,p_2 = cent(ps[i],ps[j])
                if p_1 != None: #点が離れすぎてない時だけ
                    for m in range(n):
                        if abs(p_1-ps[m]) <= 1.001:
                            ans1 += 1
                        if abs(p_2-ps[m]) <= 1.001:
                            ans2 += 1
                    ans = max(ans,ans1,ans2)
        print(ans)



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

using namespace std;

#define int long long

const int N = 1e5 + 100;
const int INF = 1e15;
int dp[N], h[N], n;

int sol(int idx) {
    if (idx == n ) return 0;
    int &ans = dp[idx];
    if (ans != -1) return ans;
    ans = INF;
    for (int i = 1; i <= 2; i++) {
        if (idx + i <= n) {
            ans = min(ans, sol(idx + i) + abs(h[idx + i] - h[idx]));
        }
    }
    return ans;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    memset(dp, -1, sizeof(dp));
    cout << sol(1) << "\n";
}

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

Measured memory_bytes: 4992
N,K = map(int,input().split())
h = [int(input()) for _ in range(N)]

a = 0
b = 0
_min = 10 ** 9

h.sort()

for i in range(K-1,len(h)):
    if _min > h[i] - h[i-K+1]:
        _min = h[i] - h[i-K+1]

print(_min)

Measured memory_bytes: 7436
#include<bits/stdc++.h>
using namespace std;
map<int,int> m;
int main(){
    int n;
    cin>>n;
    bool flag = false;
    while(n--){
        int x;
        cin>>x;
        m[x]++;
       if(m[x]>1)flag = true;

    }
    if(flag)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}


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

int main() {
  int a, b;
  cin >> a >> b;
  
  int Kake = a * b;
  int Wari = Kake /2 ;
  
  if(Kake == Wari * 2){
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <assert.h>
using namespace std;

#define NMAX 100002

char c[NMAX];
vector <int> v[NMAX];

bool possible(const int n) {
    if (c[1] == '0')
        return false;
    if (c[n] == '1')
        return false;
    for (int i = 1; i < n; i++) {
        if (c[i] != c[n - i])
            return false;
    }
    return true;
}

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

    // ifstream cin("code.in");
    cin >> (c + 1);
    const int n = strlen(c + 1);

    if (!possible(n)) {
        cout << "-1\n";
        return 0;
    }

    v[1].push_back(2);
    int current = 2;

    for (int i = 2; i <= (n >> 1); i++) {
        if (c[i] == '0')
            continue;
        int prev = current;
        while (current != i) {
            v[prev].push_back(++current);
        }
        v[prev].push_back(++current);
    }

    for (int i = current + 1; i <= n; i++) {
        v[current].push_back(i);
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (const int x : v[i]) {
            if (i < x) {
                cout << i << " " << x << '\n';
                cnt++;
            }
        }
    }
    assert(cnt == n - 1);
    return 0;
}


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

int main() {
    int n, m;
    cin >> n >> m;

    int sum = m * 1900 + (n - m) * 100;

    int cnt[6] = {1, 2, 4, 8, 16, 32};
    cout << sum * cnt[m] << endl;

    return 0;
}

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

int ceil_div(int a, int b)
{
    return (a + b - 1) / b;
}

int main()
{
    long long k, q;
    cin >> k >> q;

    vector<long long> d(k);
    for (long long &dd : d)
    {
        cin >> dd;
    }

    long long n, x, m;
    for (long long i = 0; i < q; i++)
    {
        cin >> n >> x >> m;
        long long ans = n - 1;
        long long sum = x;
        for (long long i = 0; i < k; i++)
        {
            long long diff = d[i] % m;
            if (diff == 0)
            {
                ans -= ceil_div(n - i - 1, k);
            }
            sum += ceil_div(n - i - 1, k) * diff;
        }
        cout << ans - (sum / m - x / m) << endl;
    }
}


Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(){
    long long n,k,a[2000],A=0,B=0;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
        for(int j=0;j<i;j++){
            if(a[i]>a[j]) A++;
            if(a[i]<a[j]) B++;
        }
    }
    A%=1000000007;
    B%=1000000007;
    k%=1000000007;
    long long k2=k*(k-1)/2;
    k=k*(k+1)/2;
    k%=1000000007;
    k2%=1000000007;
    long long ans=(B*k+A*k2)%1000000007;
    cout<<ans<<endl;
    return 0;
}

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

#define INF 10000000000
#define MOD 1000000007

using namespace std;

int main()
{
    int N;
    cin >> N;
    long long power = 1;
    for(int i = 1; i <= N; i++)
    {
        power *= i;
        power %= MOD;
    }

    cout << power << endl;

    return 0;
}


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

int MOD = 998244353;

ll power(ll x, ll n) {
    x %= MOD;
    //n %= MOD-1;
    int64_t ans = 1;
    while (n > 0) {
        if ((n & 1LL) == 1LL) {
            ans = ans * x % MOD;
        }
        x = x * x % MOD;  //一周する度にx, x^2, x^4, x^8となる
        n >>= 1;          //桁をずらす n = n >> 1
    }
    return ans;
}

ll mod_inv(ll x){
    return power(x, MOD-2);
}


ll factrial[100005], inverse[100005];  //階乗と逆元を保持

void init(ll n) {
    factrial[0] = 1;
    inverse[0] = 1;
    for (ll i = 1; i <= n; i++) {
        factrial[i] = (factrial[i - 1] * i) % MOD;  //階乗を求める
        inverse[i] = power(factrial[i], MOD - 2) % MOD;  //オイラーの定理で逆元を求める
    }
}

ll nCk(ll n, ll k) {
    if(n < 0 || k < 0 || n < k) return 0;
    return factrial[n] * inverse[k] % MOD * inverse[n - k] % MOD;
}


vector<ll> conb;

ll nCkbig(ll n, ll k) {
    if(conb[k] >= 0) return conb[k];
    if (k == 0)
        return 1;
    else
        return conb[k] = nCkbig(n, k - 1) * ((n - k + 1 + MOD)%MOD) % MOD * mod_inv(k) % MOD;
}

ll N, M, K;

ll calc(ll x){
    ll res = 0;
    for(ll i=0;i<x;i++){
        res += power(x-i,N)*nCk(x, x-i)%MOD * (i%2 ? -1 : 1) % MOD;
        res %= MOD;
    }
    return res;
}

int main(){
    cin >> M >> N >> K;
    conb.resize(K+1, -1);
    conb[0] = 1;
    if(M < K){
        cout << 0 << endl;
        return 0;
    }
    init(100001);
    ll ans = power(M,N);
    M %= MOD;
    for(int i=1;i<K;i++){
        ans -= calc(i)*nCkbig(M,i)%MOD;
        ans = (ans%MOD+MOD)%MOD;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 4688
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}


int calc(char op, int a,int b){
  if(op == '+') return a | b;
  if(op == '^') return a ^ b;
  if(op == '*') return a & b;
  assert(0);
}

string s;
int pos;
map<char,int> num;
int dfs(){

  if(s[pos] == '['){
    pos++;
    int res = dfs();
    assert(s[pos] == ']');
    pos++;
    return res;
  }
  else if(isalpha(s[pos])){
    int res = num[s[pos]];
    pos++;
    return res;
  }
  else if(s[pos] == '+' || s[pos] == '^' || s[pos] == '*'){
    char op = s[pos];
    pos++;
    int a = dfs();
    int b = dfs();
    return calc(op, a, b);
  }
  assert(0);
}


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  while(1){
    cin>>s;
    if(s == ".") break;
    string a;
    cin>>a;
    
    num['a'] = a[0] - '0';
    num['b'] = a[1] - '0';
    num['c'] = a[2] - '0';
    num['d'] = a[3] - '0';
    pos = 0;
    int target = dfs();
    int ans = 0;
    for(int i=0; i<= 9;i++)
      for(int j=0; j<= 9;j++)
        for(int k=0; k<= 9;k++)
	  for(int l=0; l<= 9;l++){
	    num['a'] = i;
	    num['b'] = j;
	    num['c'] = k;
	    num['d'] = l;
	    pos = 0;
	    int hash = dfs();
	    if(target == hash) ans++;
	  }
    cout<<target<<" "<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 3244
W, H, x, y = map(int, input().split())

S = W*H
ans1 = S/2
ans2 = 0
if 2*x == W or 2*y == H:
    ans2 = 0
if x == 0 or x == W or y == 0 or y == H:
    ans2 = 0
if 2*x == W and 2*y == H:
    ans2 = 1
print(ans1, ans2)


Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define vc vector<int>
#define um unordered_map<int,int>
#define ll long long 
#define rep(i,a,b) for(__typeof(a) i=a; i<b; i++)
#define si(a) a.size()
#define all(a) a.begin(),a.end()
#define ss(a) a.second
#define ff(a) a.first
#define M 1000000
#define pb push_back
#define repit(i,a) for(auto i=a.begin(); i!=a.end(); i++)
#define take(arr,n) for(int i=0;i<n;i++)cin>>arr[i]
#define out(arr,n) for(int i=0;i<n;i++)cout<<arr[i]<<' '
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define reprev(i,b,a) for(__typeof(b) i=b; i>=a; i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define doublearray vector<vector<int>>
#define mod 1000000007 
using namespace std;
ll max(ll a, ll b){ return a>b?a:b; }
ll min(ll a, ll b){ return a<b?a:b; }
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}
int binaryS(int x, int sb[], int m){
    int l = 0, r=m;
    int mid = (l+r)/2;
    while(l<r){
        mid = (l+r)/2;
        if(sb[mid]<x) l= mid+1;
        else if(sb[mid]>x) r = mid-1;
        else return mid;
    }
    return l;
}
int n,m,vis[200001]; 
int dfs(vector<vc>&g, int i, int par){
    if(vis[i]) return 0;
    int c = 0;
    vis[i]=true;
    rep(j,0,si(g[i])){
        if(g[i][j]==par) continue;
        c += dfs(g,g[i][j],i);
    }
    return c+1;
}
int main(){
    fastio;
    cin>>n>>m;
    unordered_map<int,um>mp;
    vector<vc>g(n+1);
    rep(i,0,m){
        int x,y; cin>>x>>y;
        if((mp[x].find(y)!=mp[x].end())||(mp[y].find(x)!=mp[y].end())){
            continue;
        }
        else{
            g[x].pb(y); g[y].pb(x);
            mp[x][y]++;
        }
    }
    ll maxi = 0;
    rep(i,1,n+1){
        if(!vis[i]){
            maxi = max(maxi,dfs(g,i,-1));
        }
    }
    cout<<maxi<<endl;
    return 0;
}


Measured memory_bytes: 57452
#include <bits/stdc++.h>
using namespace std;
#define Liny "Yes\n"
#define Linn "No\n"
int main(){
  char s[6]; cin>>s;
  bool r = (s[2]==s[3] && s[4]==s[5]);
  cout << (r?Liny:Linn);
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define loop(n, i) for(int i=0;i<n;i++)
#define loop1(n, i) for(int i=1;i<=n;i++)
#define rloop(n, i) for(int i=n;i;i++)
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;

int main() {
    int n; cin >> n;
    V<int> D(n);
    loop (n, i) cin >> D[i];

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

    int m = D.size() / 2;
    cout << D[m] - D[m - 1] << endl;
    return 0;
}



Measured memory_bytes: 640
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define V vector
template <typename T> bool chmin(T &a, const T &b) {if(a > b){a = b; return true;} return false;}
template <typename T> bool chmax(T &a, const T &b) {if(a < b){a = b; return true;} return false;}
V<int> dx = {-1, 1,  0, 0, -1, -1,  1, 1};
V<int> dy = { 0, 0, -1, 1, -1,  1, -1, 1};

int main () {
    int h, w, m; cin >> h >> w >> m;
    V<int> tate(w), yoko(h);
    set<P> st;
    rep(i, m) {
        int H, W; cin >> H >> W; H--; W--;
        tate[W]++; yoko[H]++;
        st.insert({W, H});
    }
    int mx1 = 0, mx2 = 0;
    rep(i, w) chmax(mx1, tate[i]);
    rep(i, h) chmax(mx2, yoko[i]);
    V<int> mx_tate, mx_yoko;
    rep(i, w) {
        if (tate[i] == mx1) mx_tate.push_back(i);
    }
    rep(i, h) {
        if (yoko[i] == mx2) mx_yoko.push_back(i);
    }
    int a = mx_tate.size(), b = mx_yoko.size();
    rep(i, a) {
        rep(j, b) {
            if (!st.count({mx_tate[i], mx_yoko[j]})) {//遅くともm+1回目で現れる
                cout << mx1 + mx2 << endl;
                return 0;
            }
        }
    }
    cout << mx1 + mx2 - 1 << endl;

    return 0;
}

Measured memory_bytes: 23704
a,b,c,d,e,f = map(int,input().split())
Water = []
Sugar = []

for i in range(0,31):
    for j in range(0,31):
        water = 100*a*i+100*b*j
        if water > f:
            break
        Water.append(water)
for i in range(f//min(c,d)+1):
    for j in range(f//min(c,d)+1):
        sugar = c*i + d*j
        if sugar > f:
            break 
        Sugar.append(sugar)
Sugar=list(set(Sugar))
Water = list(set(Water))
        

def Noudo(x,y):
    if(x>0 and y>0):
        return 100*y/(x+y)
    else:
        return 0
Max = 0
tmp_w,tmp_s = 100*a,0
for i in Water:
    for j in Sugar:
        if (i/100*e >= j) and (i+j <= f):
            tmp = Noudo(i,j)
            if Max < tmp:
                Max = tmp
                tmp_w = i+j
                tmp_s = j
print(tmp_w,tmp_s)
  



Measured memory_bytes: 12436
#include <iostream>
#include <vector>
#include<queue>
#include<iomanip>
#include<array>
using namespace std;
#define MAX 1000000000
#define ll long long


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

	int N;
	cin >> N;
	int temp=N%10;
	
	switch (temp)
	{
	case 2:
	case 4:
	case 5:
	case 7:
	case 9:
		cout << "hon";
		break;
	case 3:
		cout << "bon";
		break;
	default:
		cout << "pon";
		break;
	}
	return 0;
}

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

using namespace std;

int main(void) {
    vector<int> a(3);
    int i;
    int sum;
    for(i=0; i < 3; i++) {
        scanf("%d", &a[i]);
    }
    
    sort(a.begin(), a.end());
    
    sum = abs(a[2]-a[1]) + abs(a[1] - a[0]);

    printf("%d\n", sum);

    return 0;

}


Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;

fun main (args : Array<String>) {
  val input = Scanner(System.`in`)
  
  while (input.hasNext()) {
    val distinctElement = HashSet<Int> ()
    val N = input.nextInt()
    
    for (i in 1..N) {
      distinctElement.add(input.nextInt())
    }
    
    if (distinctElement.size == N) {
      println("YES")
    } else {
      println("NO")
    }
  }
}

Measured memory_bytes: 70924
#include <stdio.h>

int main(void)
{
	int c1,c5,c10,c50,c100,c500;
	int handan;
	
	scanf("%d %d %d %d %d %d",&c1,&c5,&c10,&c50,&c100,&c500);
	
	if((c1*1+c5*5+c10*10+c50*50+c100*100+c500*500) / 1000 > 0){
		handan = 1;
	}
	else {
		handan = 0;
	}
	
	
	printf("%d\n",handan);
	
	return(0);
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,C; cin>>n>>C;
    vector<vi> sum(C,vi(100010));
    rep(i,n){
        int s,t,c; cin>>s>>t>>c; s--; t--; c--;
        sum[c][s]++; sum[c][t+1]--;
    }
    rep(i,C)rep(j,100000){
        sum[i][j+1] += sum[i][j];
    }
    rep(i,C)rep(j,100001){
        sum[i][j] = min(1,sum[i][j]);
    }
    int ans=0;
    rep(i,100000){
        int cnt=0;
        rep(c,C) cnt+=sum[c][i];
        chmax(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 12416
#include<iostream>
#include<cstdlib>
using namespace std;
int N,d,t[2],x[2],y[2];
bool flag=1; 
int main(){
    cin>>N;
    while(N--){
        cin>>t[1]>>x[1]>>y[1];
        d=abs(x[1]-x[0])+abs(y[1]-y[0]);
        flag*=((t[1]-t[0]>=d&(t[1]-t[0]-d)%2==0)?1:0);              
        swap(x[0],x[1]);
        swap(y[0],y[1]);                          
        swap(t[0],t[1]);
         
    }   
    cout<<(flag?"Yes":"No")<<"\n";
    return 0;
     
}


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

#define IN 1;
#define OUT -1;

struct data{string time;int io;};
//bool operator<(data a,data b){return a.time<b.time?1:a.io<b.io;}
bool operator<(data a,data b){return a.time!=b.time?a.time<b.time:a.io<b.io;}

int main()
{
  int n,i,cnt,max;
  vector<data> v;
  while(cin>>n,n){
    v.resize(2*n);
    for(i=0;i<2*n;i+=2){
      cin>>v[i].time>>v[i+1].time;
      v[i].io=IN;
      v[i+1].io=OUT;
    }
    sort(v.begin(),v.end());
    for(cnt=max=i=0;i<2*n;i++){
      cnt+=v[i].io;
      if(max<cnt)max=cnt;
    }
    cout<<max<<endl;
  }
}

Measured memory_bytes: 1724
using System;
using System.Linq;

namespace AtCoder
{
    class Abc160D
    {
        public static void Main()
        {
            var nxy = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            int n = nxy[0];
            int x = nxy[1];
            int y = nxy[2];

            // y-x+1のringと1:x , y:Nを考える

            int xside = x - 1;
            int yside = n - y;
            int ring = y - x + 1;
            int half = ring / 2;

            Console.WriteLine(n);

            bool isEvenRing = ring % 2 == 0;
            for (int d = 2; d < n; d++)
            {
                int xn = Line(xside, d);
                int yn = Line(yside, d);
                int hn = Line(half, d);
                int rn = ring > d * 2 ? ring :
                         ring == d * 2 ? d : 0;
                int count = xn + yn + rn;

                count += 2 * (Line(xside + half, d) - xn - hn);
                count += 2 * (Line(yside + half, d) - yn - hn);
                if (isEvenRing && d > half)
                {
                    int diff = d - half;
                    if (diff <= xside)
                        count--;
                    if (diff <= yside)
                        count--;
                }
                if (xside > 0 && yside > 0)
                    count += Line(xside + yside + 1, d) - Line(xside + 1, d) - Line(yside + 1, d);
                Console.WriteLine(count);
            }
        }

        public static int Line(int length, int distance)
        {
            int t = length - distance + 1;
            return t > 0 ? t : 0;
        }
    }
}


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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int t; cin>>t; while(t--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();

    int n, c=0;
    cin>> n;
    int a[n];

    for(int i=0; i<n; i++)
        cin>> a[i];

    for(int i=1; i<n-1; i++)
    {
        if( (a[i]> a[i-1]&& a[i]< a[i+1]) || (a[i]> a[i+1]&& a[i]< a[i-1]))
            c++;
    }

    cout << c;
    nl;

    return 0;
}




Measured memory_bytes: 3632
import java.util.Scanner;
 
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		S = S.replaceAll("eraser", "");
		S = S.replaceAll("erase", "");
		S = S.replaceAll("dreamer", "");
		S = S.replaceAll("dream", "");
		if (S.length() == 0){
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
		sc.close();
	}
}

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

int main() {
  int N;
  long long ten=1,nine=1,eight=1;
  cin>>N;
  rep(i,N){ten=(ten*10)%MOD;
          nine=(nine*9)%MOD;
          eight=(eight*8)%MOD;}
  ten=(2*MOD+ten-2*nine+eight)%MOD;  
  cout<<ten<<endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <cmath>
#include <map>
#include <algorithm>
#include <stack>
#include <cstring>
 
#define ll long long
#define MP make_pair
#define PB push_back
#define P push
#define f first
#define se second
#define S size()
#define B begin()
#define E end()
#define rB rbegin()
#define rE rend()
#define PI acos(-1)

 
const int N = 1e5 + 100;
const int M = 1e6 + 100;
const ll oo = 1e18;
 
ll n, m, k, t, q, h, a, b, d, c, e, w, x, y, z;
using namespace std;


int wi[1000], val[1000];
ll dp[109][N];



int main() {


	cin >> n >> w;


	for(int i = 1; i <= n; i++){
		cin >> wi[i] >> val[i];
	}




	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= w; j++){
			dp[i][j] = dp[i - 1][j];
			if(wi[i] <= j) dp[i][j] = max(dp[i][j], val[i] + dp[i - 1][j - wi[i]]);
		}
	}


	cout << dp[n][w];



    return 0;
}




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

int main() {
  int N, M;
  cin >> N>>M;
  int ac=0;
  int wa=0;
  vector<vector<int>> c(N, vector<int>(2));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 2; j++) {
      c.at(i).at(j)=0;
    }
  }
  while(M--){
    int p;
    string s;
    cin>>p>>s;
  
  
  
      if (s=="AC"){
        c.at(p-1).at(0)=1;
      }
      if (s=="WA"&&c.at(p-1).at(0)==0){
        c.at(p-1).at(1)++;
      }
  
  }
  
  for (int i = 0; i < N; i++) {
    ac+=c.at(i).at(0);
  }
  for (int i = 0; i < N; i++) {
    if(c.at(i).at(0)==1){
      wa+=c.at(i).at(1);
    }
    
  }
  
    cout<<ac<<" "<<wa<<endl;
  
}

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

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

using namespace std;

inline int popcount(int x){
	x=((x>>1)&0x55555555)+(x&0x55555555);
	x=((x>>2)&0x33333333)+(x&0x33333333);
	x=((x>>4)+x)&0x0f0f0f0f;
	x+=(x>>8);
	x+=(x>>16);
	return x&0x3f;
}

template<class G>
class Fenwick_tree{
	vector<G> a;
public:
	Fenwick_tree(int n):a(n){}
	void add(int i,G val){
		for(i++;i<=a.size();i+=i&-i) a[i-1]+=val;
	}
	G sum(int l,int r)const{
		if(l==0){
			G res{};
			for(;r>0;r-=r&-r) res+=a[r-1];
			return res;
		}
		return sum(0,r)-sum(0,l);
	}
	int lower_bound(G val)const{
		if(val<=G{}) return 0;
		int x=0,k;
		for(k=1;k<=a.size();k<<=1);
		for(k>>=1;k>0;k>>=1) if(x+k<=a.size() && a[x+k-1]<val) val-=a[x+k-1], x+=k;
		return x;
	}
	int upper_bound(G val)const{
		if(val<G{}) return 0;
		int x=0,k;
		for(k=1;k<=a.size();k<<=1);
		for(k>>=1;k>0;k>>=1) if(x+k<=a.size() && a[x+k-1]<=val) val-=a[x+k-1], x+=k;
		return x;
	}
};

template<class T>
long long inversion_number(const vector<T>& a){
	auto X=a;
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());

	long long res=0;
	Fenwick_tree<int> F(X.size());
	rep(i,a.size()){
		int x=lower_bound(X.begin(),X.end(),a[i])-X.begin();
		res+=F.sum(x+1,X.size());
		F.add(x,1);
	}
	return res;
}

const int INF=1<<29;

int main(){
	int n; scanf("%d",&n);
	vector<int> a(n),b(n);
	rep(i,n) scanf("%d",&a[i]);
	rep(i,n) scanf("%d",&b[i]);

	int ans=INF;
	rep(S,1<<n) if(popcount(S)==(n+1)/2) {
		int ne=0,no=0;
		pair<int,int> even[9],odd[9];
		rep(i,n){
			if(S>>i&1) even[ne++]={i%2==0?a[i]:b[i],i};
			else       odd [no++]={i%2==1?a[i]:b[i],i};
		}

		sort(even,even+ne);
		sort(odd ,odd +no);

		bool ok=true;
		rep(i,ne) if( i <no && even[i].first>odd [ i ].first) ok=false;
		rep(i,no) if(i+1<ne && odd [i].first>even[i+1].first) ok=false;
		if(!ok) continue;

		vector<int> p(n);
		rep(i,n) p[i]=(i%2==0?even:odd)[i/2].second;

		ans=min(ans,(int)inversion_number(p));
	}
	printf("%d\n",ans<INF?ans:-1);

	return 0;
}


Measured memory_bytes: 256
data SegmentTree m = Leaf m  | Node m (SegmentTree m) (SegmentTree m) Int
    deriving (Eq, Show)

val :: SegmentTree m -> m
val (Leaf v)     = v
val (Node v _ _ _) = v

update :: (Monoid m) => SegmentTree m  -> Int -> m -> SegmentTree m
update (Leaf v) _ x = Leaf x
update (Node v l r size)  i x
    | i < n'   =   Node (val left `mappend` val r) left r n'
    | otherwise =   Node (val l `mappend` val right) l right n'
    where n' = size `div` 2
          left = update l  i x
          right = update r (i-n') x

query :: (Monoid m) => SegmentTree m -> Int -> Int -> m

query (Leaf v) 0 1 = v
query (Node v l r size) a b
    | a >= b    = mempty
    | a == 0 && b == size   = v
    | b <= n'             = query l  a b
    | a >= n'                = query r  (a-n') (b-n')
    | otherwise             = query l  a n' `mappend` query r 0 (b-n')
    where n' = size `div` 2

resize :: Int -> Int -> Int
resize n m
    | m < n = resize n (2*m)
    | otherwise  = m


fromList :: Monoid m => [m] -> SegmentTree m
fromList xs =
    let n = length xs
        m = resize n 1
        plus = replicate (m-n) mempty
        xs' = xs ++ plus
    in fromList' xs' m

fromList' ::Monoid m => [m] -> Int ->SegmentTree m
fromList' _ 0 = Leaf mempty
fromList' [x] 1 = Leaf x
fromList' xs n = Node (val left `mappend` val right) left right n
    where n' = n `div` 2
          (xs1,xs2) = splitAt n' xs
          left = fromList'  xs1 n'
          right = fromList' xs2 (n-n')

get :: Monoid m => SegmentTree m -> Int -> m
get tree i= query tree i (i+1)

newtype Gcd = Gcd Int deriving (Eq,Ord,Read)

instance Show Gcd where
  show (Gcd x) = show x
instance Semigroup Gcd where
  Gcd x <> Gcd y = Gcd (gcd x y)

instance Monoid Gcd where
  mempty = Gcd 0

main = do
  n <- read <$> getLine
  a <- map (Gcd . read) . words <$> getLine 
  let seg = fromList a
  print $ maximum $ [query seg 0 i <> query seg (i+1) n | i <- [0..n]]

Measured memory_bytes: 135860
#include <stdio.h>
#include <string.h>
typedef long long ll;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define max(l,r) (l>r?l:r)
#define min(l,r) (l<r?l:r)
#define swap(l,r) {ll tp=l;l=r;r=tp;}
const ll MOD = 1000000007;

int main(){
    char s[105]; scanf("%s",s);
    int n = strlen(s);

    int ans = MOD;
    rep(i,26){
        int cnt[105] = {0};
        rep(j,n){
            if(s[j] != ('a'+i)){
                if(j > 0) cnt[j] = cnt[j-1] + 1;
                else cnt[j] = 1;
            }
        }
        int mx = 0;
        rep(j,n) mx = max(mx, cnt[j]);
        ans = min(ans, mx);
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 1700
#include <iostream>
#include <vector>

using lint = long long;
constexpr int X = 100000;

void solve() {
    std::vector<lint> cnt(X + 1, 0);

    int n;
    std::cin >> n;

    lint sum = 0;
    while (n--) {
        int x;
        std::cin >> x;
        sum += x;
        ++cnt[x];
    }

    int q;
    std::cin >> q;
    while (q--) {
        int x, y;
        std::cin >> x >> y;

        sum += cnt[x] * (y - x);
        cnt[y] += cnt[x];
        cnt[x] = 0;

        std::cout << sum << "\n";
    }
}

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

    solve();

    return 0;
}


Measured memory_bytes: 3908
a, b = gets.split(" ").map!{|i| i.to_i}
s = gets.chomp.chars
#p s
if s[a] == "-"
#  puts "-OK"
  cnt = 0
  for i in 0...a do
    if s[i].to_i.to_s == s[i]
      cnt += 1
#      puts "aOK"
    else
#      puts "alos"
    end
  end
  for i in a + 1..a + b do
    if s[i].to_i.to_s == s[i]
      cnt += 1
#      puts "bOK"
    else
#      puts "blos"
    end
  end
#  puts cnt
  if cnt == a + b
    puts "Yes"
  else
    puts "No"
  end
else
  puts "No"
end


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

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

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

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

  vector<int> a(3);
  for(int i=0;i<3;++i){
    scanf("%d",&a.at(i));
  }
  int num_5=0;
  int num_7=0;
  for(int i=0;i<3;++i){
    if(a.at(i)==5) num_5++;
    if(a.at(i)==7) num_7++;
  }
  if(num_5==2 && num_7==1){
    printf("YES");
   }else{
    printf("NO");
  }
}


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

#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
#define  P = pair<int, int>;



int main(){
    int n; cin >> n;
    vector<int> a(n);

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

    map<int, int> ma;

    rep(i,n){
        ma[a[i]-1]++;
        ma[a[i]]++;
        ma[a[i]+1]++;
    }

    int ans = 0;
    for(auto p : ma){
        ans = max(ans, p.second);
    }
    cout << ans << endl;
}


Measured memory_bytes: 5120
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <numeric>
#include <deque>
using namespace std;
typedef long long int ll;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    int q; cin >> q;
    while(q--){
        string t,r; int a,b;
        cin >> t;
        if(t=="print"){
            cin >> a >> b;
            cout << s.substr(a,b-a+1) << endl;
        }else if(t=="replace"){
            cin >> a >> b >> r;
            int j=0;
            for(int i=a;i<=b;i++){
                s[i]=r[j];
                j++;
            }
        }else{
            cin >> a >> b;
            r=s.substr(a,b-a+1);
            reverse(r.begin(),r.end());
            s=s.substr(0,a)+r+s.substr(b+1);
        }
    }
}


Measured memory_bytes: 3208
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<bitset>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N,a[101];
	scan(N);
	rep(i,N) scan(a[i]);
	sort(a,a+N);
	int amin=a[0],amax=a[N-1];
	int anum[101]={};
	rep(i,N) anum[a[i]]++;
	int flag=1;
	for(int i=amin+1;i<=amax;i++){
		if(anum[i]<=1) flag=0;
	}
	if((amax+1)/2!=amin) flag=0;
	if(amax%2){
		if(anum[amin]!=2) flag=0;
	}
	else{
		if(anum[amin]!=1) flag=0;
	}
	if(flag) prin("Possible");
	else prin("Impossible");
	return 0;
}


Measured memory_bytes: 256
from itertools import product
s = ['S', 'H', 'C', 'D']
n = [str(x) for x in range(1, 14)]
f = set(product(s, n))
N, *C = open(0).read().split()
g = set(zip(*[iter(C)]*2))
for p, q in sorted(f-g, key=lambda c: s.index(c[0])*13+n.index(c[1])):
    print(p + ' ' + q)



Measured memory_bytes: 5616
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;

int main()
{
	int n, k, x, sum = 0;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> x;
		sum += min(x, k - x);
	}
	cout << sum * 2 << endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define ALL(X) X.begin(), X.end()
#define SZ(A) int((A).size())
#define RALL(X) X.rbegin(), X.rend()
#define FOR(B) for (size_t i = 0; i < B; i++)
#define FORE(B) for (size_t i = 1; i <= B-1; i++)
#define FORC(A, B) for (size_t i = A; i < B; i++)
#define PRINT(X) cout << X << endl
#define PRINTALL(E, X) { FOR(X) {cout << E[i] << endl; } }
#define READALL(V, N) FOR(N) {int x; cin >> x; V.push_back(x); }
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL>VLL;
typedef vector<PII> VPII;
typedef map<int, int> MII;
typedef map<string, int> MSI;


bool hasDivisors(int q){
    int count = 0;
    for(int x = 1; x <= q; x++){
        if(q % x == 0){
            count++;
        }
        if(count > 8){
            x = q;
        }
    }
    if(count == 8)
        return true;
    else
        return false;
}

int main() {
   
    int n = 0;
    cin >> n;
    int amount = 0;
    for(int q = 1; q <= n; q+=2){
        if(hasDivisors(q)){
            amount++;
        }
    }
    cout << amount << endl;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
from decimal import Decimal
#d = Decimal('1.1')
N=int(input())
N=Decimal(N)
if N%2!=0:
    print(0)
else:
    ans=0
    for i in range(1,27):
        ans+=int((N//Decimal(5**i)/2))
    print(Decimal(ans))

Measured memory_bytes: 60908
#include<bits/stdc++.h>
using namespace std;
const int M=101;
int n,A[M];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
	double ans=0;
	for(int i=1;i<=n;i++)ans+=1.0/A[i];
	ans=1.0/ans;
	printf("%.7lf\n",ans);
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int n,m,x,y,i,a[]={-1,-1,-1};
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        if(a[x-1]==-1 || a[x-1]==y) a[x-1]=y;
        else{
            printf("-1");
            return 0;
        }
    }
    if(n!=1 && a[0]==0){
        printf("-1");
        return 0;
    }
    if(n==1 && a[0]==-1) a[0]=0;
    if(n!=1 && a[0]==-1) a[0]=1;
    for(i=0;i<n;i++){
        if(a[i]==-1) printf("0");
        else printf("%d",a[i]); 
    }
    return 0;
}

Measured memory_bytes: 128
#define _USE_MATH_DEFINES 
#include<iomanip> 
#include<cmath>  
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<queue>
#include<deque>
#include<stack>
using namespace std;
typedef long long ll;
#define repi(i,a,b) for(ll i = (ll)(a) ; i < (ll)(b) ; i++)
#define repd(i,a,b) for(ll i = (ll)(a) ; i > (ll)(b) ; i--)
#define rd(x) cin >> x
#define wr(x)  cout << x
#define wrln(x) cout << x << endl
#define wl() cout << endl
const ll MAX_10p5 = 100010;
const ll MAX_10p9 = 1000000010;
const ll MAX_10p18 = 1000000000000000010;
const ll MOD = 1000000007;
const ll m4x[4] = { 1,0,-1,0 };
const ll m4y[4] = { 0,1,0,-1 };
const ll m8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const ll m8y[8] = { 0,1,1,1,0,-1,-1,-1 };
const ll m9x[9] = { 1,1,0,-1,-1,-1,0,1,0 };
const ll m9y[9] = { 0,1,1,1,0,-1,-1,-1,0 };

struct edge {
	ll from, to, cost;
	bool operator<(const edge& right) const {
		return cost < right.cost;
	}
};
struct point {
	ll x, y;
	bool operator<(const point& right) const {
		return x == right.x ? y < right.y : x < right.x;
	}
};

///////////////////////////////////////////////////////////////////////////////////////

ll N, ans;
point pr[110], pb[110];

int main() {
	rd(N);
	repi(i, 0, N) cin >> pr[i].x >> pr[i].y;
	repi(i, 0, N) cin >> pb[i].x >> pb[i].y;
	sort(pr, pr + N);
	sort(pb, pb + N);
	repi(i, 0, N) {
		ll index = -1;
		repi(j, 0, N) {
			if (pr[j].x > pb[i].x) break;
			if (pr[j].y < pb[i].y) index > -1 ? (pr[index].y < pr[j].y ? index = j : index = index) : index = j;
		}
		if (index > -1) {
			ans++;
			pr[index].y = MAX_10p18;
		}
	}
	wrln(ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>

using namespace std;

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

/*
    freopen("input","r",stdin);
    freopen("output","w",stdout);
*/

int main() {
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> R(N);
    for (int i = 0;i < N;i++) cin >> R[i];
    sort(R.begin(), R.end());
    int B = R[N - 1];
    if (B == 1) {
        if (R.size() == 2 && R[0] == B) cout << "Possible" << endl;
        else cout << "Impossible" << endl;
        return 0;
    }
    unordered_map<int, int> H;
    for (int i = 0;i < N;i++) H[R[i]]++;
    int S = (B + 1) / 2;
    if (R[0] != S) {
        cout << "Impossible" << endl;
        return 0;
    }
    for (int i = B;i > S;i--) {
        H[i]--;
        if (H[i] < 0) {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    H[S]--;
    if (B % 2) H[S]--;
    if (H[S] != 0) {
        cout << "Impossible" << endl;
        return 0;
    }
    cout << "Possible" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    int dp[55][55][55];
    fill(dp[0][0], dp[55][0], 1000);
    dp[A][B][C] = 0;
    for(int a = 0; a < 53; ++a) {
        for(int b = 0; b < 53; ++b) {
            for(int c = 0; c < 53; ++c) {
                int tmp = dp[a][b][c] + 1;
                chmin(dp[a][b + 1][c + 1], tmp);
                chmin(dp[a + 1][b][c + 1], tmp);
                chmin(dp[a + 1][b + 1][c], tmp);
                chmin(dp[a + 2][b][c], tmp);
                chmin(dp[a][b + 2][c], tmp);
                chmin(dp[a][b][c + 2], tmp);
            }
        }
    }
    int ans = 1000;
    for(int i = 0; i < 55; ++i) {
        chmin(ans, dp[i][i][i]);
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
     
    using namespace std;
    const long long INF = 1LL <<60;  
     
    long long gcn(long long x,long long y){
      if(x%y==0){
        return y;
      }
      else{
        return gcn(y,x%y);
      }
    }
     
    int main(void){
      long res=0;
      long long n,m;
      long tmp;
      long long i,j,k;
      
      cin>>n;
      long l[n];
      for(i=0;i<n;i++){
        cin>>l[i];
      }
      sort(l,l+n);
      for(i=0;i<n-2;i++){
        //cout<<i<<endl;
        for(j=i+1;j<n-1;j++){
          tmp=l[i]+l[j];
          //cout<<i<<j<<tmp<<endl;
          for(k=j+1;(l[k]<tmp && k<n);k++){
            //cout<<i<<j<<k<<l[i]<<l[j]<<l[k]<<endl;
            if((l[i]+l[k]>l[j]) && (l[j]+l[k]>l[i])){
              res++;
            }
          }
        }
      }
      
      cout<<res<<endl;
      return 0;
    }

Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int main()
{
	vector<string> strs;
	int n, a_num = 0, b_num = 0, both_num = 0, ans = 0;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		strs.emplace_back();
		cin >> strs.back();
	}

	for (auto& str : strs)
	{
		if (str[0] == 'B' && str[str.size() - 1] == 'A')
		{
			/*if (a_num > b_num)
				++b_num;
			else if (a_num == b_num)
			{
				++ans;
			}
			else
				++a_num;*/
			++both_num;
		}
		else if (str[0] == 'B')
		{
			++b_num;
		}
		else if (str[str.size() - 1] == 'A')
		{
			++a_num;
		}

		for (int i = 0; i < str.size() - 1; ++i)
		{
			if (str[i] == 'A' && str[i + 1] == 'B')
			{
				++ans;
			}
		}
	}


	if (both_num)
	{
		ans += both_num - 1;//ここ終了時には最初がBで最後がA

		if (a_num)//最初にくっつける
		{
			++ans;
			--a_num;
		}

		if (b_num)//最後にくっつける
		{
			++ans;
			--b_num;
		}
	}

	//あとは好きにしろ

	ans += a_num > b_num ? b_num : a_num;

	cout << ans;

	return 0;
}

Measured memory_bytes: 768
#include<cstdio>

using namespace std;

int c[26];

int check(){
	for(int i = 0; i < 26; i++) if(c[i] & 1) return 0;
	return 1;
}

int main(){
	char w[110]; scanf("%s", w);
	for(int i = 0; w[i] != '\0'; i++) c[w[i] - 'a']++;
	puts(check() ? "Yes" : "No");
	return 0;
}

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
ll A[200100];

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

  std::cin >> N;

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

  ll sum = std::accumulate(A, A + N, 0ll);
  ll s = 0;
  ll res = std::numeric_limits<ll>::max();

  for(int i=0;i+1<N;++i){
      s += A[i];

      res = std::min(res, std::max(s, sum - s) - std::min(s, sum - s));
  }

  std::cout << res << std::endl;
}


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

using namespace std;

int A,B,C,X,ans;

int main(){
    cin>>A>>B>>C>>X;
    for(int i=0;i<=A;i++){
        for(int j=0;j<=B;j++){
            for(int k=0;k<=C;k++){
                if(500*i+100*j+50*k==X)ans++;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#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; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size)
#define MOD 1000000007
const long long mod = 1e9+7;
typedef vector<long long> Vl;
typedef vector<double> VI;  // VI a(n);
typedef vector<string> VS;  
typedef vector<VS> VSS;  
typedef vector<VI> VVI;   // VVI a(n,vector<int>(m)) n * m 
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef long long ll;  //ll とdoubleは違う
// cout << << endl;
// cin >> ;
int main(){
    ll k=0,s=0,n,min=100000000000,ans=0,max=0;
    string s1,s2,s3;
    cin >> n >> s1;
    rep(i,s1.size()){
        if (s1[i]=='I'){
            ans++;
        }
        else {
            ans--;
        }
        if(max<ans) max = ans;
    }
    
    cout << max << endl;
    return 0;
}

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

void insertionSort(int num[100], int N) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (num[i] < num[j]) {
				int temp = num[i];
				for (int k = i; k > j; k--) {
					num[k] = num[k - 1];
				}
				num[j] = temp;
			}
		}
		for (int j = 0; j < N; j++) {
			cout << num[j];
			if (j != N - 1) {
				cout << " ";
			}
		}
		cout << endl;
	}
}

int main(void){
	int N, num[100];

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	insertionSort(num, N);

	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

#define MIN(a, b) ((a<b) ? a : b)

//降順
int des(const void *a, const void *b) {
  return *(int *)b - *(int *)a;
}

int main() {
  int n;
  scanf("%d", &n);
  int a[n], l, r, s=1000000000;
  for (int i=0; i<n; i++) scanf("%d", a+i);
  qsort(a, n, sizeof(int), des);
  l=a[0];
  if (l%2 == 1) {
    for (int i=1; i<n; i++) {
      int sub = MIN(abs(a[i]-l/2), abs(a[i]-l/2-1));
      if (s>sub) {
        s=sub;
        r=a[i];
      }
    }
  } else {
    for (int i=1; i<n; i++) {
      int sub = abs(a[i]-l/2);
      if (s>sub) {
        s=sub;
        r=a[i];
      }
    }
  }
  printf("%d %d\n", l, r);
  return 0;
}


Measured memory_bytes: 1020
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int n,k;
string s;
int main(){
    cin>>n>>k;
    cin>>s;
    int x=0;
    for(int i=0;i+1<n;i++)if(s[i]=='R'&&s[i+1]=='L')x++;
    int y=(s[0]=='L'?1:0)+(s[n-1]=='R'?1:0);
    x+=y;
    if(x-k<1)x=1;
    else{x-=k;k=0;}
    y=min(y,x);
    if(k)y=1;
    x-=y;
    cout<<n-2*x-y<<endl;
    return 0;
}

Measured memory_bytes: 512
# APC001C - Vacant Seat
def main():
    # if no vacant seat in [0, i)
    # -> seat[0] == seat[i] if i % 2 else seat[0] != seat[i]
    N = int(input())
    print(0, flush=1)
    seat_zero = input().rstrip()
    if seat_zero == "Vacant":
        return
    left, right = 0, N
    for _ in range(19):
        mid = (left + right) // 2
        print(mid, flush=1)
        this_seat = input().rstrip()
        if this_seat == "Vacant":
            return
        if mid % 2 == (seat_zero != this_seat):
            left = mid
        else:
            right = mid


if __name__ == "__main__":
    main()

Measured memory_bytes: 3660
#include <cstdio>
#include <cstring>

#define R register
#define maxn 110
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
char s[maxn];
bool p[maxn];
int main()
{
	scanf("%s", s);
	R int ans = 0x7fffffff, n = strlen(s);
	for (R int aph = 0; aph < 26; ++aph)
	{
		R bool flag = 0;
		for (R int i = 0; i < n; ++i) flag |= p[i + 1] = (s[i] == aph + 'a');
		if (!flag) continue;
		for (R int i = 1; i <= n; ++i) flag &= p[i];
		if (flag) {puts("0"); return 0;}
		for (R int i = 1; i < n; ++i)
		{
			flag = 1;
			for (R int j = 1; j <= n - i; ++j)
				flag &= (p[j] |= p[j + 1]);
			if (flag)
			{
				cmin(ans, i);
				break;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128