akhauriyash/Code-Regression huggingface dataset:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
    def size(self,x):
      return -self.parents[self.find(x)]
    
    def roots(self):
      return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
      return len(self.roots())
    
n,m = map(int,input().split())  
uf = UnionFind(n)

for i in range(m):
  a, b = map(int,input().split())
  uf.union(a-1,b-1)
print(uf.group_count()-1)

Measured memory_bytes: 12820
#include <cstdio>

bool p[50][50];

int main()
{
  char s[50][51];
  int h, w;
  scanf("%d%d", &h, &w);
  for (int i = 0; i < h; ++i)
  {
    scanf("%s", s[i]);
  }
  const int dir[] = {0, 1, 0, -1, 0};
  for (int y = 0; y < h; ++y)
  {
    for (int x = 0; x < w; ++x)
    {
      if (p[y][x] || s[y][x] == '.') continue;
      bool r = false;
      for (int i = 0; i < 4; ++i)
      {
        int X = x + dir[i + 1];
        int Y = y + dir[i];
        if (0 <= X && X < w && 0 <= Y && Y < h && s[Y][X] == '#')
        {
          p[Y][X] = true;
          r = true;
        }
      }
      if (!r)
      {
        puts("No");
        return 0;
      }
    }
  }
  puts("Yes");
  return 0;
}

Measured memory_bytes: 128
n, m = map(int, raw_input().split())

a = []
for i in range(n):
    a.append(map(int, raw_input().split()))
b = []
for j in range(m):
    b.append(int(raw_input()))

ans = []
for i in range(n):
    tmp = 0
    for j in range(m):
        tmp += a[i][j] * b[j]
    ans.append(tmp)

print "\n".join(map(str, ans))

Measured memory_bytes: 6532
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int N, K;
  cin >> N >> K;
  int ret = 0;
  rep(i,N){
    int h;
    cin >> h;
    if(h >= K) ret++;
  }

  cout << ret << endl;
  
  return 0;
}


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

long long N, M, n, m, A, B, a[1001][1001], l, r, i, j;
string s = ".<>^v";

int main(){
    scanf("%lld%lld%lld%lld", &N, &M, &A, &B);
    n = N;
    m = M;
    n & 1 && --n;
    m & 1 && --m;
    if(N * M == 2 * (A + B) + 1 && ((A - m / 2) & (B - n / 2)) & 1){
        for(i = 0; i < m - 2 && A > 0; i += 2){
            --A;
            a[n][i] = 1;
            a[n][i + 1] = 2;
        }
        for(i = 0; i < n - 2 && B > 0; i += 2){
            --B;
            a[i][m] = 3;
            a[i + 1][m] = 4;
        }
        [&]{
            for(i = 0; i < n; i += 2){
                for(j = 0; j < m; j += 2){
                    if(i >= n - 1 && j >= m - 1)return 0;
                    if(A > 2){
                        a[i][j] = 1;
                        a[i][j + 1] = 2;
                        --A;
                        if(A <= 2)continue;
                        a[i + 1][j] = 1;
                        a[i + 1][j + 1] = 2;
                        --A;
                        if(A <= 2)continue;
                    }else if(B > 2){
                        a[i][j] = 3;
                        a[i + 1][j] = 4;
                        --B;
                        if(B <= 2)return 0;
                        a[i][j + 1] = 3;
                        a[i + 1][j + 1] = 4;
                        --B;
                        if(B <= 2)return 0;
                    }else return 0;
                }
            }
            return 1;
        }();
        A -= 2;
        B -= 2;
        a[n - 2][m - 2] = a[n][m - 1] = 1;
        a[n - 2][m - 1] = a[n][m] = 2;
        a[n - 2][m] = a[n - 1][m - 2] = 3;
        a[n - 1][m] = a[n][m - 2] = 4;
    }else{
        if(N & 1){
            for(i = 0; i < m && A > 0; i += 2){
                --A;
                a[n][i] = 1;
                a[n][i + 1] = 2;
            }
        }
        if(M & 1){
            for(i = 0; i < n && B > 0; i += 2){
                --B;
                a[i][m] = 3;
                a[i + 1][m] = 4;
            }
        }
        [&]{
            for(i = 0; i < n; i += 2){
                for(j = 0; j < m; j += 2){
                    if(A > 0){
                        a[i][j] = 1;
                        a[i][j + 1] = 2;
                        --A;
                        if(A <= 0)continue;
                        a[i + 1][j] = 1;
                        a[i + 1][j + 1] = 2;
                        --A;
                        if(A <= 0)continue;
                    }else if(B > 0){
                        a[i][j] = 3;
                        a[i + 1][j] = 4;
                        --B;
                        if(B <= 0)return 0;
                        a[i][j + 1] = 3;
                        a[i + 1][j + 1] = 4;
                        --B;
                        if(B <= 0)return 0;
                    }else return 0;
                }
            }
            return 1;
        }();
    }
    if(A || B)return 0 & puts("NO");
    puts("YES");
    for(int i = 0; i < N; ++i, puts(""))
        for(int j = 0; j < M; ++j)
            printf("%c", s[a[i][j]]);
    return 0;
}

Measured memory_bytes: 9088
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;

string S;

int main()
{
    int A,B;

    cin >> A >> B;

    cin >> S;

    for(int i = 0;i < S.size();i++)
    {
        if(i == A)
        {
            if(S[i] != '-')
            {
                cout << "No" << endl;
                return 0;
            }
        }
        else
        {
            if(S[i] == '-')
            {
                cout << "No" << endl;
                return 0;

            }
        }
    }

    cout << "Yes" << endl;
    return 0;
    
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    if N%1000 == 0:
        print(0)
    else:
        print(1000 - N%1000)
if __name__ == '__main__':
    main()

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

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

char input[70][70];
string dp[70][70];

int comp(string s,string t) {
  if(s.length() != t.length()) return (s.length() - t.length());
  rep(i,s.length()) if(s[i] != t[i]) return (s[i] - t[i]);
  return 0;
}

int main() {
  int w,h,n;
  while(cin>>w>>h, w|h) {
    string s,above,left;
    rep(i,h) {
      cin>>s;
      rep(j,w) {
	dp[i][j] = "";
	input[i][j] = s[j];
      }
    }

    rep(i,h) rep(j,w) {
      char c = input[i][j];
      if(!(c <= '9' && c >= '0')) continue;
      above = ((i > 0 && dp[i-1][j] != "0") ? dp[i-1][j] : "") + string(1,c);
      left = ((j > 0 && dp[i][j-1] != "0") ? dp[i][j-1] : "") + string(1,c);
      dp[i][j] = (comp(above,left) <= 0) ? left : above;
      //if(dp[i][j][0] == '0') dp[i][j] = dp[i][j].substr(1);
    }

    string ans = "";
    rep(i,h) rep(j,w) if(comp(ans,dp[i][j]) < 0) ans = dp[i][j];
    cout<<ans<<endl;
  }
}

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

#define             ll  long long
#define             vi  vector<int>
#define             vl  vector<ll>
#define             PI  acos(-1.0)
#define            vii  vector<pair<int, int> >
#define            vll  vector<pair<ll, ll> >
#define            ull  unsigned long long
#define            pii  pair<int, int>
#define            pll  pair<ll, ll>
#define            P_B  push_back
#define            M_P  make_pair
#define         DBG(x)  printf("%s %d\n", #x, x)
#define         SCI(x)  scanf("%d",&x)
#define         SCD(x)  scanf("%lf",&x)
#define         SCS(x)  scanf("%s",x)
#define         CLR(x)  memset(x, 0, sizeof(x))
#define        CLRN(x)  memset(x, -1, sizeof(x))
#define        SCLL(x)  scanf("%lld", &x)
#define       DBGLL(x)  printf("%s %lld\n", #x, x)
#define      FOR(i, n)  for(int i = 0; i < n; i++)
#define     SCI2(m, n)  scanf("%d%d", &m, &n)
#define     SCD2(m, n)  scanf("%lf%lf",&m,&n)
#define    SCLL2(m, n)  scanf("%lld%lld", &m, &n)
#define  FORR(i, m, n)  for(int i = m; i < n; i++)
#define  SCI3(m, n, o)  scanf("%d%d%d",&m, &n, &o)
#define  SCD3(m, n, o)  scanf("%lf%lf%lf",&m,&n,&o)
#define SCLL3(m, n, o)  scanf("%lld%lld%lld",&m, &n, &o)

#define            MOD  1000000007
#define            INF  1000000000


int main()
{
	int h1, m1, h2, m2, k;
	SCI2(h1, m1);
	SCI3(h2, m2, k);
	int x, y;
	if(m1 > m2){
		x = m2+60-m1;
		y = h2-h1-1;
	}
	else{
		x = m2-m1;
		y = h2-h1;
	}
	printf("%d\n", x+y*60-k);
}


Measured memory_bytes: 3824
K = int(input())
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
sum = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(i,j,k)

print(sum)


Measured memory_bytes: 69536
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cctype>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <sstream>
#include <complex>
#include <fstream>
#include <functional>
#include <numeric>
#include <utility>
#include <algorithm>
#include <assert.h>
#include <unordered_map>

using namespace std;
const int N = 6e5 + 500;
const int LN = 21;
const long long mod = 1e9 + 7;
const long long INF = 1LL << 57;

long long n, m, u, v, k, t, q, a, x, d, b;



vector <int> queries[N];
vector <long long> cst[N];
vector <int> adj[N];
vector <long long> color[N];
long long col[N], cost[N];
long long sol[N];

int tin[N], tout[N], H = 0, L[N][LN], D[N];
void dfs(int v, int p, int d) {
   tin[v] = ++H;
   L[v][0] = p;
   D[v] = d;
   for (int i = 1; i < LN; ++i) {
      L[v][i] = L[L[v][i - 1]][i - 1];
   }
   for (int u : adj[v]) {
      if (u == p) continue;
      dfs(u, v, d + 1);
   }
   tout[v] = ++H;
}

int lca(int u, int v) {
   if (D[v] > D[u]) swap(u, v);
   int diff = D[u] - D[v];
   for (int i = 0; i < LN; ++i) {
      if (diff & (1 << i))
         u = L[u][i];
   }
   if (u == v) return u;
   for (int i = LN - 1; i >= 0; --i) {
      if (L[u][i] != L[v][i]) {
         u = L[u][i];
         v = L[v][i];
      }
   }
   return L[u][0];
}


map <int, int> cnt;
map <int, long long> dist;

void solve(int v, int p, long long curdist) {
   
   for (int i: queries[v]) {
      long long add = 1;
      if (i < 0) add = -2;
      i = abs(i);
      sol[i] += add * (curdist + (cnt[col[i]] * cost[i] - dist[col[i]]));
   }
   
   for (int i = 0; i < adj[v].size(); ++i) {
      int u = adj[v][i];
      if (u == p) continue;
      cnt[color[v][i]]++;
      dist[color[v][i]] += cst[v][i];
      solve(u, v, curdist + cst[v][i]);
      cnt[color[v][i]]--;
      dist[color[v][i]] -= cst[v][i];
   }
   
}


int main() {
   ios::sync_with_stdio(false);cin.tie(0);
   cin >> n >> q;
   
   for (int i = 0; i < n - 1; ++i) {
      cin >> u >> v >> a >> k;
      adj[u].push_back(v);
      adj[v].push_back(u);
      color[u].push_back(a);
      color[v].push_back(a);
      cst[u].push_back(k);
      cst[v].push_back(k);
   }
   
   dfs(1, 0, 0);
   
   for (int i = 1; i <= q; ++i) {
      cin >> col[i] >> cost[i] >> u >> v;
      queries[u].push_back(i);
      queries[v].push_back(i);
      queries[lca(u, v)].push_back(-i);
      //cout << u << " " << v << " " << lca(u, v) << endl;
   }
   
   solve(1, 0, 0);
   
   for (int i = 1; i <= q; ++i) {
      cout << sol[i] << '\n';
   }
}







Measured memory_bytes: 109180
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007

using namespace std;

typedef long long ll;

string A, B;

int L[2050];
int R[2050];

int mx1[2050];
int mx2[2050];
int getans()
{
    int N = A.size(), i, j;
    for (i = 0; i < N; i++)
        if (B[i] == '1')
            break;
    if (i >= N)
    {
        for (i = 0; i < N; i++)
            if (A[i] == '1')
                return (1<<30);
        return 0;
    }

    for (i = 0; i < N; i++)
    {
        for (j = i;; j--)
            if (B[(j + N) % N] == '1')
                break;
        L[i] = j;
        for (j = i;; j++)
            if (B[j%N] == '1')
                break;
        R[i] = j;
    }

    int rv = (1<<30);
    for (i = 0; i < N; i++)
    {
        vector <pair<int, int> > Vu;
        int x = i;
        for (j = 0; j < N; j++)
        {
            if (A[j] == B[(j - i + N) % N])
                continue;
            x++;

            int s = -i + j, e = j;
            if (L[e] >= s)
                continue;

            Vu.pb({R[e] - e, (s+N)%N - L[(s+N)%N]});
        }
        sort(Vu.begin(), Vu.end());

        mx1[0] = 0;
        for (j = 0; j < Vu.size(); j++)
            mx1[j + 1] = max(mx1[j], Vu[j].first);
        mx2[Vu.size()] = 0;
        for (j = (int)Vu.size() - 1; j >= 0; j--)
            mx2[j] = max(mx2[j + 1], Vu[j].second);

        for (j = 0; j <= Vu.size(); j++)
            rv = min(rv, x + 2 * (mx1[j] + mx2[j]));
    }
    return rv;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> A;
    cin >> B;
    int n = A.size();
	int ans = getans();
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());
	ans = min(ans, getans());
	if(ans == (1<<30))
        cout << -1;
    else
        cout << ans;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
#define PI 3.141592653589793
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}

const int MOD = 1000000007;

class UnionFind{
public:
  //親の番号を格納する変数。数値がマイナスの場合は親であり、その絶対値のサイズのグループを持っている
  vector<int> Parent;
  
  //コンストラクタ。-1で初期化する。
  UnionFind(int N){
    Parent = vector<int>(N,-1);
  }
  
  //Aが何処のグループに属しているか返す
  int root(int A){
    if(Parent[A] < 0) return A; //0以下の時は自分が親。自分のグループなので自分を返す
    return Parent[A] = root(Parent[A]); //根でなかった場合は再帰的に関数を呼ぶ。ついでにParent[A]を更新して次の時高速化する。
  }
  
  //自分の親の頂点数を返す。マイナスでグループのサイズを持っているので反転して返す。
  int size(int A){
    return -Parent[root(A)];
  }
  
  //AとBを連結する関数
  bool connect(int A, int B){
    A = root(A); //Aの親を持ってくる
    B = root(B); //Bの親を持ってくる
    if (A==B){ //親が同じだったらくっつけない
      return false;
    }
    
    //Aが必ず大きい数にする
    if (size(A) < size(B)) swap(A,B);
    
    //AにBのグループをくっつける。
    Parent[A] += Parent[B];
    //Bの親をAにする。
    Parent[B] = A;
    
    return true;
  }
};

struct edge{
  int u,v,cost;
};

vector<edge> es;
int n;

bool comp(const edge &e1, const edge &e2){
  return e1.cost < e2.cost;
}

int kruskal(){
  sort(es.begin(),es.end(),comp);
  UnionFind uf(n);
  int res = 0;
  for(auto e:es){
    if(uf.root(e.u) != uf.root(e.v)){
      uf.connect(e.u,e.v);
      res += e.cost;
    }
  }
  
  return res;
}

int main(){
  cin >> n;
  vector<tuple<int,int,int>> t(n);
  rep(i,n){
    int x,y; cin >> x >> y;
    t[i] = make_tuple(x,y,i);
  }
  
  sort(t.begin(),t.end());
  
  rep(i,n-1){
    int x1,x2,y1,y2,u,v;
    tie(x1,y1,u) = t[i];
    tie(x2,y2,v) = t[i+1];
    edge e;
    e.u = u, e.v = v;
    e.cost = min(abs(x1-x2),abs(y1-y2));
    es.push_back(e);
  }
  
  rep(i,n){
    int x,y,id;
    tie(x,y,id) = t[i];
    t[i] = make_tuple(y,x,id);
  }
  
  sort(t.begin(),t.end());
  
  rep(i,n-1){
    int x1,x2,y1,y2,u,v;
    tie(x1,y1,u) = t[i];
    tie(x2,y2,v) = t[i+1];
    edge e;
    e.u = u, e.v = v;
    e.cost = min(abs(x1-x2),abs(y1-y2));
    es.push_back(e);
  }
  
  cout << kruskal() << endl;
    
  return 0;
}

Measured memory_bytes: 6004
#include<iostream>
#include<cmath>

using namespace std;

typedef long long ll;

int Q;

int main() {
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		ll A, B;
		cin >> A >> B;
		if (A == B) {
			cout << (A - 1) * 2 << endl;
		}
		else {
			ll root = sqrtl(A * B - 1);
			ll ans = root * 2 - 1;
			if ((A * B - 1) / root == root)ans--;
			cout << ans << endl;
		}

	}
	return 0;
}


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

const int MAXN = 200005;

int n, v[20];
int a[MAXN];
int f[20][MAXN], g[20][MAXN];

int fl[1<<20|1], fr[1<<20|1];

int main()
{
	scanf("%d%d", &n, &v[0]);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int lev = 0;
	for (int i = 0; ; i++) {
		lev = i;
		f[i][n+1] = n+1;
		g[i][0] = 0;
		for (int j = n; j >= 1; j--) {
			f[i][j] = j;
			if (j < n && a[j+1]-a[j] <= v[i])
				f[i][j] = f[i][j+1];
		}
		for (int j = 1; j <= n; j++) {
			g[i][j] = j;
			if (j > 1 && a[j]-a[j-1] <= v[i])
				g[i][j] = g[i][j-1];
		}
		if (v[i] == 0) break;
		v[i+1] = v[i]>>1;
	}
	fl[0] = 0, fr[0] = n+1;
	for (int i = 1; i < 1<<(lev+1); i++) {
		fl[i] = 1, fr[i] = n;
		for (int k = 0; k <= lev; k++)
			if (i>>k&1) {
				fl[i] = max(fl[i], f[k][fl[(i^(1<<k))]+1]);
				fr[i] = min(fr[i], g[k][fr[(i^(1<<k))]-1]);
			}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (f[0][i] != f[0][i-1])
			cnt++;
	}
	// cerr << cnt << " " << lev+1 << endl;
	if (cnt > lev+1) {
		for (int i = 1; i <= n; i++) puts("Impossible");
	} else {
		int last = 0;
		for (int i = 1; i <= n; i++) {
			if (f[0][i] != f[0][i-1]) {
				// cerr << i << endl;
				int tot = (1<<(lev+1))-1-1;
				last = 0;
				for (int j = tot; j >= 0; j = (j-1)&tot) {
					// cerr << j << " " << (tot^j) << " " << fl[j] << " " << fr[tot^j] << endl;
					if (fl[j] >= i-1 && fr[tot^j] <= f[0][i]+1) {
						last = 1;
						break;
					}
					if (j == 0) break;
				}
			}
			if (last == 0) puts("Impossible");
			else puts("Possible");
		}
	}
	return 0;
}


Measured memory_bytes: 42112
#include<bits/stdc++.h>
using namespace std;
#pragma region Macros
#define ios\
    ios::sync_with_stdio(false);\
    cin.tie(nullptr);
#define VEC(type, name, size)\
    V<type> name(size);\
    IN(name)
#define VVEC(type, name, h, w)\
    VV<type> name(h, V<type>(w));\
    IN(name)
#define INT(...)\
    int __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LL(...)\
    ll __VA_ARGS__;\
    IN(__VA_ARGS__)
#define STR(...)\
    string __VA_ARGS__;\
    IN(__VA_ARGS__)
#define CHAR(...)\
    char __VA_ARGS__;\
    IN(__VA_ARGS__)
#define DOUBLE(...)\
    DOUBLE __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LD(...)\
    LD __VA_ARGS__;\
    IN(__VA_ARGS__)
template <class T> void scan(T &a) { cin >> a; }
template <class T> void scan(vector<T> &a) { for(auto &i : a) scan(i); }
template <class T, class L> void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &... tail) { scan(head); IN(tail...); }
template <class T> inline void print(T x){ cout << x << '\n';}
#define ll long long
#define ld long double
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}}
template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}}
template<class T> T Roundup_div(T x, T y) {return (x+(y-1))/y;}
template <typename T> T pow(T a, long long n, T e = 1) {T ret = e; while (n) {if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; }
const ll INF = 1e18;
#pragma endregion

const int M = 301;

ll dp[301][301][301];

int main(){
    ios;
    INT(n, k);
    VEC(ll, h, n);
    REP(i, M) REP(j, M) REP(t, M) dp[i][j][t] = INF;
    dp[0][0][0] = 0;
    REP(i, n) REP(j, i + 1) REP(t, i + 1){
        chmin(dp[i + 1][j][t], dp[i][j][t]);
        chmin(dp[i + 1][j + 1][i + 1], dp[i][j][t] + max(h[i] -(t ? h[t - 1] : 0), 0ll));
    }
    ll res = INF;
    REP(t, M) chmin(res, dp[n][n - k][t]);
    print(res);
}

Measured memory_bytes: 216716
#include<stdio.h>
#include<string.h>

int main(){
  char s[13],t[14];
  scanf("%s\n",s);
  scanf("%s\n",t);
  int k,l,m,count=0;
  k=strlen(s);
  l=strlen(t);
     if(l-k==1){
      for(int i=0;i<k;i++)
      if(s[i]==t[i])
      count++;
      else break;
      if(count==k)
      printf("Yes");
      else
      printf("No");
     }
  else printf("No");
 
} 

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

using ll = long long;
using ull = unsigned long long;

#define MOD 1000000007

int main(void) {
    ll x;
    ll count;
    cin >> x;
    count = 2 * (x / 11);
    if(x % 11 != 0) {
        count++;
        if(x % 11 >= 7) count++;
    } 
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))

Int a[216000], b[216000];

int main(){
  Int n, p;
  cin >> n;
  for(Int i = 0;i < n;i++){
    cin >> p;p--;
    a[p]+=i;
    if(p+1 < n)
      b[p+1]-=i;
  }
  for(Int i = 1;i < n;i++)a[i] += a[i-1], b[i] += b[i-1];
  for(Int i = 0;i < n;i++){
    cout << 1 + i + a[i] << " ";
  }cout << endl;
  
  for(Int i = 0;i < n;i++){
    cout << 1000000000 - i + b[i] << " ";
  }cout << endl;
  
  return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>

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

using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
    int N; cin >> N;
    int M; cin >> M;
    vector<int> H(N); rep(i, N) cin >> H[i];
    
    vector<bool> ok(N, true);
    
    rep(i, M) {
        int A, B;
        cin >> A >> B;
        A--; B--;
        if (H[A] <= H[B]) ok[A] = false;
        if (H[B] <= H[A]) ok[B] = false;
    }

    int ans = 0;
    rep(i, N) if(ok[i]) ans++;

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


Measured memory_bytes: 3788
import itertools
import math
n=int(input())
lis=[list(map(int,input().split())) for i in range(n)]
num=[j for j in range(n)]
new=list(itertools.permutations(num))
ans=0
for i in range(len(new)):
    for j in range(n-1):
        a=new[i][j]
        b=new[i][j+1]
        
        ans+=math.sqrt((lis[a][0]-lis[b][0])**2+(lis[a][1]-lis[b][1])**2)
        
print(ans/len(new))

Measured memory_bytes: 7972
import math
#n,m = map(int,input().split())
x = int(input())

prime_list = []
if x!=1:
    for i in range(2,int(math.sqrt(x))+1):
        j = 2
        while i**j<=x:
            prime_list.append(i**j)
            j+=1

    print(max(prime_list))
else:
    print(1)


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		int[][][] man_num;
		man_num = new int[4][3][10];

		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();

		for (int i = 0; i < n; i++) {
			int b = scan.nextInt();
			int f = scan.nextInt();
			int r = scan.nextInt();
			int v = scan.nextInt();

			man_num[b - 1][f - 1][r - 1] = man_num[b - 1][f - 1][r - 1] + v;
		}
		
		
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 10; j++) {
				System.out.print(" "+man_num[0][i][j]);
			}
			System.out.println();
		}
		
		for (int i = 0; i < 1; i++) {
			for (int j = 0; j < 20; j++) {
				System.out.print("#");
			}
			System.out.println();
		}
		
		
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 10; j++) {
				System.out.print(" "+man_num[1][i][j]);
			}
			System.out.println();
		}
		
		for (int i = 0; i < 1; i++) {
			for (int j = 0; j < 20; j++) {
				System.out.print("#");
			}
			System.out.println();
		}
		
		
		
		
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 10; j++) {
				System.out.print(" "+man_num[2][i][j]);
			}
			System.out.println();
		}
		
		for (int i = 0; i < 1; i++) {
			for (int j = 0; j < 20; j++) {
				System.out.print("#");
			}
			System.out.println();
		}
		
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 10; j++) {
				System.out.print(" "+man_num[3][i][j]);
			}
			System.out.println();
		}
		
		
		
	}

}

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

int ans, n, x[52], y[52];

int solve(int a,int b){
	int cnt = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (i == j)continue;
			if (x[i] - x[j] == a && y[i] - y[j] == b)cnt++;
		}
	}
	return cnt;
}


int main(){
	
	cin >> n;

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

	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (i == j)continue;
			ans = max(ans, solve(x[i] - x[j], y[i] - y[j]));
		}
	}

	cout << n - ans << endl;

	 return 0;
	
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);

		while(true) {
			int H = sc.nextInt();
			int W = sc.nextInt();
			if(H == 0 || W == 0) break;

			/*for(int i = 0; i < H; i++) {
				for(int j = 0; j < W; j++) {
					if(i % 2 == 0) {
						if(j % 2 == 0) {
							System.out.print("#");
						} else {
							System.out.print(".");
						}
					} else {
						if(j % 2 == 0) {
							System.out.print(".");
						} else {
							System.out.print("#");
						}
					}
				}
				System.out.println();
			}
			System.out.println();*/

			for(int i = 0; i < H; i++) {
				for(int j = 0; j < W; j++) {
					if((i + j) % 2 == 0) {
						System.out.print("#");
					} else {
						System.out.print(".");
					}
				}
				System.out.println();
			}
			System.out.println();
		}


	}

}



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

int main() {
  int N, M;
  int sum = 0;

  cin >> N;
  vector<int> T(N);
  rep(i, N) {
    cin >> T[i];
    sum += T[i];
  }

  cin >> M;
  vector<int> P(M), X(M);
  rep(i, M) {
    cin >> P[i];
    cin >> X[i];
  }

  rep(i, M) {
    cout << sum - T[P[i] - 1] + X[i] << endl;
  }
}

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

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

    if (c >= b) {
        if (a+b >= c) {
            ans = b + c;
        }
        else {
            ans = a + 2*b + 1;
        }
    }
    else {
        ans = b + c;
    }
    cout << ans << endl;
   
    return 0;
}

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

int main() {
  
  int N,A;
  
  cin >> N >> A;
  
  if (N % 500 <= A) {
    cout << "Yes" << endl;
  }
  
  if (N % 500 > A) {
    cout << "No" << endl;
  }
        
}

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

#define debug(s) cout << s << endl
#define debug1(s, t) cout << s << " " << t << endl
#define debug2(s, t, u) cout << s << " " << t << " " << u << endl
#define printvec(v)       \
    for (auto &&i : v)    \
        cout << i << " "; \
    cout << endl
#define rep(n, i) for (int i = 0; i < n; i++)

using namespace std;
using i64 = long long;

int main()
{
    string s;
    cin >> s;

    string ans = "ABC";
    if (s=="ABC") ans = "ARC";
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    double n; cin >> n;
    cout << n*3.14159*2 << endl;
    return 0;
}

Measured memory_bytes: 3784
#include <stdio.h>
#include <math.h>

int main(void){
	int input;
	scanf("%d", &input);
	
	int second = input % 60;
	input /= 60;
	int minute = input % 60;
	input /= 60;	
	
	int hour = 0;
	if(input > 24){
		hour = input / 24;
	}
	else{
		hour = input;
	}
	
	printf("%d:%d:%d\n", hour, minute, second);
}


Measured memory_bytes: 2748
import sys

def gcd(a,b):
    if b==0:
        return a
    return(gcd(b, a%b))

def lcm(a,b):
    return (a*b)//gcd(a,b)

N, M = map(int,input().split())
S = input()
T = input()
d = gcd(N,M)
L = lcm(N,M)
for i in range(d):
    if S[i*(N//d)] != T[i*(M//d)]:
        print(-1)
        sys.exit()

print(L)


Measured memory_bytes: 3316
// package Contest#176;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        String str = br.readLine();
        int sum = 0;
        for(int i=0; i<str.length(); i++){
            sum += str.charAt(i)-'0';
        }

        if(sum % 9 == 0){
            out.println("Yes");
        }else{
            out.println("No");
        }
        out.close();
    }
}

Measured memory_bytes: 36520
package main
 
import "fmt"
 
func main() {
  weather := ""
  fmt.Scan(&weather)
  switch weather {
  case "Sunny":
    fmt.Println("Cloudy")
  case "Cloudy":
    fmt.Println("Rainy")
  case "Rainy":
    fmt.Println("Sunny")
  default:
    fmt.Println("No season")
  }
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<cstdio>

using namespace std;

int main()
{
	int H, W;
	vector<string> s;
	string str, ans = "Yes";	
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		cin >> str;
		s.push_back(str);
	}


	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (s[i][j] == '#') {
				if (i - 1 >= 0 && s[i - 1][j] == s[i][j]) {
					continue;
				}else if(i + 1 <= H-1 && s[i + 1][j] == s[i][j]) {
					continue;
				}else if(j - 1 >= 0 && s[i][j - 1] == s[i][j]) {
					continue;
				}else if(j + 1 <= W-1 && s[i][j + 1] == s[i][j]) {
					continue;
				}else {
					ans = "No";
				}
			}
		}
	}

	cout << ans;

	char qq;
	cin >> qq;
	return 0;
}

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

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

    int64_t sum=0;
    for (int64_t i=1;i<N+1;i++){
        if (i%3!=0 and i%5!=0){
            sum+=i;
        }
    }
    cout << sum << endl;
}

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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

int main() {
  int n, k, x, y;
  cin >> n >> k >> x >> y;
  cout << min(n, k) * x + max(n - k, 0) * y << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int n,k;
    cin >> n >> k;
    int r,s,p;
    cin >> r >> s >> p;
    string t;
    cin >> t;
    vector<bool> win(n, false);
    ll ans = 0;
    for(int i=0;i<n;i++){
        if(i >= k && win[i-k] && t[i-k] == t[i]) continue;         
        switch(t[i]){
            case 'r': ans += p;break;
            case 's': ans += r;break;
            case 'p': ans += s;break;
        }
        win[i] = true;
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
<?php
// From https://qiita.com/yoshikyoto/items/6924478283dbdd549e4b
class Scanner {
    private $arr = [];
    private $count = 0;
    private $pointer = 0;
    public function next() {
        if($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }
    public function hasNext() {
        return $this->pointer < $this->count;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
}
// From https://qiita.com/yoshikyoto/items/6924478283dbdd549e4b


list($N,$D)=sscanf(trim(fgets(STDIN)),"%d %d");
$X = array();
for($j=1;$j<=$N;$j++){
    $sc = new Scanner();
    for($i=1;$i<=$D;$i++){
        $X[$j][$i] = $sc->nextInt();
    }
}
$sum = 0;
$cnt = 0;
for($i=1;$i<=$N;$i++){
    for($j=$i+1;$j<=$N;$j++){
        for($k=1;$k<=$D;$k++){
            $sum += pow(($X[$i][$k]-$X[$j][$k]),2);
        }
        $sum = sqrt($sum);
        if(preg_match('/^[0-9]+$/', $sum)){
            $cnt++;
        }
        $sum = 0;
    }
}
printf($cnt);

//$n = $sc->nextInt();

Measured memory_bytes: 5496
#include <bits/stdc++.h>
#define ll long long 
#define intm INT_MAX
#define llm LONG_LONG_MAX

using namespace std;
int MOD = 13;


//ll red[100030];
//ll green[100030];
//ll colorless[200030];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int x,y,a,b,c;
	ll ans = 0;
	cin >> x >> y >> a >> b >> c;
	priority_queue<ll> red;
	priority_queue<ll> green;
	priority_queue<ll, vector<ll>, greater<ll> > eaten;
	priority_queue<ll> colorless;
	ll tmp;
	for(int i=1; i <= a; i++){
		cin >> tmp; red.push(tmp);
	}	
	for(int i=1; i <= b; i++){ cin >> tmp; green.push(tmp); }
	for(int i=1; i <= c; i++){ cin >> tmp; colorless.push(tmp); }
	for(int i=1; i <= x; i++){
		ans += red.top(); eaten.push(red.top()); red.pop();
	}	
	for(int i=1; i <=y; i++){
		ans += green.top(); eaten.push(green.top()); green.pop();
	}	
	while( !eaten.empty() && !colorless.empty() && (colorless.top() > eaten.top())  ){
		ans -= eaten.top(); ans += colorless.top();
		eaten.pop(); colorless.pop();
	}	
	cout << ans;
	
	
		
}



Measured memory_bytes: 4852
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ll 				long long
#define int             long long int
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define modp            998244353
#define inf             (ll)1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define FIO           	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl 			'\n'
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int r, c, k;
int dp[3001][3001][4];
int cost[3001][3001];

int solve(int i, int j, int item_row)
{
	if(i == r-1 && j == c-1)
	{
		if(item_row < 3 && cost[i][j])
			return cost[i][j];
		return 0;
	}
	if(i >= r)
		return INT_MIN;
	if(j >= c)
		return INT_MIN;
	if(dp[i][j][item_row] != -1)
		return dp[i][j][item_row];
	int x = INT_MIN, y = INT_MIN, z = INT_MIN, w = INT_MIN;
	if(cost[i][j] && item_row < 3)
	{
		x = cost[i][j]+solve(i, j+1, item_row+1);
		y = cost[i][j]+solve(i+1, j, 0);
		z = solve(i, j+1, item_row);
		w = solve(i+1, j, 0);
	}
	else
	{
		x = solve(i, j+1, item_row);
		y = solve(i+1, j, 0);
	}
	return dp[i][j][item_row] = max({x, y, z, w});
}


void solve()
{
	cin >> r >> c >> k;
	memset(cost, 0, r*c);
	for(int i = 0; i < k; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		x--;y--;
		cost[x][y] = z;
	}
	memset(dp, -1, sizeof dp);
	cout << solve(0, 0, 0) << endl;
}
 
int32_t main()
{
	FIO
    // w(t)
    {
    	solve();
    }
    return 0;
}
	

	

Measured memory_bytes: 356032
#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();}
template<class T> inline T sqr(T x) {return x*x;}
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef pair<int, int> PII;
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(v, n) sort(v, v+n)
#define VSORT(v) sort(v.begin(), v.end())
#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define INF 999999999
const double EPS = 1e-10;
const double PI  = acos(-1.0);
#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;

int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int h,w,n;
    cin >>h>>w>>n;
    ll cnt=0;
    ll sum=0;
    REP(i,min(h,w)){
        REP(j,max(h,w)){
            cnt++;
            sum+=max(h,w);
            if(sum>=n){
                cout<<cnt<<endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    float a,b,t,t2;
    cin>>a>>b>>t;
    float total=0;
    t2=t+0.5;
    float ans=0;
    while(total<t2)
    {
        //ans+=b;
        //cout<<total<<endl;
        total+=a;
        if(total>t2)
            break;
        ans+=b;

    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int n,m;
	int sum=0;
	int MAX=-1;
	cin>>n>>m;
	int a,b;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		if(a<n){
			MAX=max(n-a,MAX);
			sum+=n-a;
		}
	}
	cout<<sum-MAX<<endl;
	return 0;
}


Measured memory_bytes: 3104
#include<iostream>
#include<string.h>
using namespace std;
int main(){
	int n,m;
	while(cin>>n>>m){
		int a[n+1][m+1];
		memset(a,0,sizeof(a));
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>a[i][j];
				a[i][m]+=a[i][j];
				a[n][j]+=a[i][j];
			}
		}
		for(int i=0;i<m;i++){
			a[n][m]+=a[n][i];
		}
		for(int i=0;i<n+1;i++){
			for(int j=0;j<m+1;j++){
				if(j==0)
					cout<<a[i][j];
				else
					cout<<" "<<a[i][j];
			}
			cout<<endl;
		}
	}
	return 0;
} 


Measured memory_bytes: 3144
//This disgusting code is wriiten by Juruo D0zingbear
//Please don't hack me! 0v0 <3
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#include <assert.h>
#define LL long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piii pair<int, pii >
#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define vi vector<int>
#define vpi vector< pii >
#define INF 2147483647
#define big 19260817
#define pb push_back
#define mp make_pair
using namespace std;
const int Maxk=1005;
string mul(string a,string b){
	int res[Maxk];
	memset(res,0,sizeof(res));
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for (int i=0;i<a.length();i++){
		for (int j=0;j<b.length();j++){
			res[i+j]+=(a[i]-'0')*(b[j]-'0');
		}
	}
	for (int i=0;i<Maxk;i++){
		if (res[i]>=10) {
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	string ret;
	bool flag=false;
	for (int i=Maxk-1;i>=0;i--){
		if (flag || res[i]){
			flag=true;
			ret=ret+(char)(res[i]+'0');
		}
	}
	if (ret=="") ret="0";
	return ret;
}
string add(string a,string b){
	if (a.length()<b.length()) swap(a,b);
	while (a.length()!=b.length()){
		b='0'+b;
	}
	for (int i=a.length()-1;i>=0;i--){
		a[i]+=(b[i]-'0');
		if (a[i]>'9' && i){
			a[i]-=10;
			a[i-1]++;
		}
	}
	if (a[0]>'9'){
		a[0]-=10;
		a='1'+a;
	}
	return a;
}

// cf IO: I64d
// atcoder IO: ｌｌｄ
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int Maxn=105;
int a[Maxn],n;
multiset<int> x;
int main(){
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		scanf("%d",&a[i]);
	} 
	sort(a,a+n);
	if (a[n-1]!=a[n-2]){
		printf("Impossible\n");
		return 0;
	}
	for (int i=0;i<n-2;i++){
		x.insert(a[i]);
	}
	int num=a[n-1]-1;
	for (int i=1;i<=num;i++){
		int xx=max(i,num+1-i);
		if (x.find(xx)==x.end()){
			printf("Impossible\n");
			return 0;
		}
		x.erase(x.find(xx));
	}
	if (!x.empty() && (*x.begin())<=(num)/2+1){
		printf("Impossible\n");
		return 0;
	}
	printf("Possible\n");
	return 0;
}

Measured memory_bytes: 256
#E
N=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(N)]
ALL=A[0]
for i in range(1,N):
    ALL^=A[i]

for i in range(N):
    B[i]=A[i]^ALL
B=map(str,B)
print(" ".join(B))    

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

using namespace std;

int N;
int arr[104], ans[104];

int main(){
    scanf("%d", &N);
    for(int i = 1; i < N; ++i){
        scanf("%d", arr + i);
        ans[i] = ans[i + 1] = (int)1e9;
    }
    int sum = 0;
    for(int i = N - 1; i >= 1; --i){
        ans[i + 1] = min(ans[i + 1], arr[i]);
        ans[i] = min(ans[i], arr[i]);
        sum += ans[i + 1];
    }
    printf("%d\n", sum + ans[1]);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	static ll n;
	static ll a[100010];
	static ll b[100010];
	scanf("%lld",&n);
	rep1(i,n){
		scanf("%lld",&a[i]);
	}
	rep1(i,n){
		scanf("%lld",&b[i]);
	}
	
	vector<ll> X,Y;
	ll sum_X = 0, sum_Y = 0;
	rep1(i,n){
		if(a[i] < b[i]){
			X.push_back(b[i]-a[i]);
			sum_X += b[i]-a[i];
		}
		if(a[i] > b[i]){
			Y.push_back(a[i]-b[i]);
			sum_Y += a[i]-b[i];
		}
	}
	if(sum_X > sum_Y){
		puts("-1");
		return 0;
	}
	
	int ret = X.size();
	sum_Y = 0;
	sort(Y.begin(),Y.end());
	reverse(Y.begin(),Y.end());
	for(int i = 0 ; sum_Y < sum_X ; i ++){
		sum_Y += Y[i];
		ret ++;
	}
	cout << ret << endl;
}



Measured memory_bytes: 2936
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long B = sc.nextLong();
		long N = sc.nextLong();
		long x = Math.min(B-1, N);
		System.out.println(A*x/B - A*(x/B));

	}

}

Measured memory_bytes: 35696
//In The Name Of The God

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define F first
#define S second
#define X first.first
#define Y first .second
#define A second.first
#define B second.second
#define mp make_pair
#define pb push_back
#define pf push_front
#define P push
#define pob pop_back
#define pof pop_front
#define PO pop
#define rep(i,j,k) for(int i = j ; i <= k ; ++ i)
#define rrep(i,j,k) for(int i = j ; i>=k ; --i)
#define FR(i,j,k) for(int i = j ; i < k ; ++ i )
#define rFR(i,j,k) for(int i = j ; i > k ; -- i )
#define lb(x) x&-x
#define p2(x) (1LL<<x)
#define SZ size()
#define LB lower_bound
#define UB upper_bound
#define IT iterator
#define RIT reverse_iterator
#define E end()
#define BE begin()
#define RE rend()
#define RBE rbegin()
#define UN unsigned

typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll ;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
typedef pair<int,pll> pipl;
typedef pair<pll,int> ppli ;
typedef pair<pll,pll> plpl ;
typedef pair<ll,pii> lpip;
typedef pair<pii,ll> lppi;
typedef pair<pii,pii> lppp;
typedef pair<ll,pll> lpipl;
typedef pair<pll,ll> lppli ;
typedef pair<pll,pll> lplpl ;
typedef vector<int> vi ;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef set<int> sti;
typedef set<ll> stl;
typedef set<pii > stpi;
typedef set<pll> stpl;
typedef vi::IT vit;
typedef vl::IT vlt;
typedef vpi::IT vpit;
typedef vpl::IT vplt;
typedef sti::IT stit;
typedef stl::IT stlt;
typedef stpi::IT stpit;
typedef stpl::IT stplt;
typedef vpi::RIT rvpit;
typedef vpl::RIT rvplt;
typedef sti::RIT rstit;
typedef stl::RIT rstlt;
typedef stpi::RIT rstpit;
typedef stpl::RIT rstplt;

const int MAXN = 500000;
const int SUPERN = 5000000;
const int MAXS = 325;
const int SUPERS = 1000;
const int MD = 1e9+7;
//......Structures.......

//......Variables........
ll n,a[MAXN],s,l,r,k,x;
//......Funcs............
ll sum(ll a,ll b)
{
    return (a+b)%MD;
}
ll mu(ll a,ll b)
{
    return (a*b)%MD;
}
ll mn(ll a,ll b)
{
    return(a-b+MD)%MD;
}
//......Code.............
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    rep(i,1,n)cin>>a[i];
    sort(a+1,a+n+1);

    if(a[n]<k)
    {
        cout<<"IMPOSSIBLE";
        return 0;
    }
    x=a[n]-k;
    l=1,r=2;
    if(x==0)
    {
        cout<<"POSSIBLE";
        return 0;
    }
    while(r<=n)
    {
        s+=a[r]-a[r-1];
        while(s>x)
        {
            s-=a[l+1]-a[l];
            l++;
        }
        //cout<<s<<endl;
        if(s!=0&&x%s==0)
        {
            cout<<"POSSIBLE";
            return 0;
        }
        r++;
    }
    cout<<"IMPOSSIBLE";
    return 0;
}


Measured memory_bytes: 1024