akhauriyash/Code-Regression huggingface dataset:
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v) {std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

//const
#define EPS 1e-8
#define EQ (abs((a) - (b)) < EPS)
#define EQP(a, b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )

inline int signum(double x) { return (abs(x) < EPS) ? 0 : (x > 0) ? 1 : -1; }

//-----definition-----
typedef complex<double> P;

//-----standard-----
pair<P, P> norm_vec(P a) {
    return make_pair(a * P(0, 1), a * P(0, -1));
}

P unit_vec(P a) { a / abs(a); }

double dot(P a, P b) {
    return a.real() * b.real() + a.imag() * b.imag();
}

double cross(P a, P b) {
    return a.real() * b.imag() - a.imag() * b.real();
}

int ccw(P a, P b, P c) {
    b -= a;
    c -= a;
    int sign = signum(cross(b, c));
    if (sign != 0) return sign;
    if (signum(dot(b, c)) < 0) return -2;//left
    if (abs(b) < abs(c)) return 2;//right
    return 0; //mid
}

//-----line-----
bool is_paral(P a1, P a2, P b1, P b2) {
    return signum(cross(a2 - a1, b2 - b1)) == 0;
}

bool is_orth(P a1, P a2, P b1, P b2) {
    return signum(dot(a2 - a1, b2 - b1)) == 0;
}

bool is_p_on_li(P a, P b, P c) {
    b -= a;
    c -= a;
    return signum(cross(b, c)) == 0;
}

bool is_p_on_li_s(P a, P b, P c) {
    return abs(c - a) + abs(b - c) < abs(b - a) + EPS;
}

double dis_p_li(P a, P b, P c) {
    b -= a;
    c -= a;
    return abs(cross(b, c)) / abs(b);
}

double dis_p_li_ss(P a, P b, P c) {
    P x1 = b - a;
    P y1 = c - a;
    P x2 = a - b;
    P y2 = c - b;
    if (cross(x1, y1) < EPS) return abs(y1);
    if (cross(x2, y2) < EPS) return abs(y2);
    return dis_p_li(a, b, c);
}

bool is_inter_li_ss(P a1, P a2, P b1, P b2) {
    return (ccw(a1, a2, b1) * ccw(a1, a2, b2) <= 0) && (ccw(b1, b2, a1) * ccw(b1, b2, a2) <= 0);

}

int main() {

    int Q;
    cin >> Q;

    while (Q--) {

        vector<P> p(4);
        for (int i = 0; i < 4; i++) {
            double x, y;
            cin >> x >> y;
            p[i] = P(x, y);
        }

        if (is_inter_li_ss(p[0], p[1], p[2], p[3])) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }

    }

}















































Measured memory_bytes: 3288
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
typedef long long int lint;
using namespace std;

// Warshall_Floyd
// dは隣接行列
template <typename T>
void warshall_floyd(vector<vector<T>>& d) {
    int n = d.size();
    T T_max = numeric_limits<T>::max();
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][k] == T_max || d[k][j] == T_max) continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main() {
    int n, m, l;
    cin >> n >> m >> l;
    lint M = LLONG_MAX;
    vector<vector<lint>> d(n, vector<lint>(n, M));
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        d[a][b] = c;
        d[b][a] = c;
    }
    for (int i = 0; i < n; i++) {
        d[i][i] = 0;
    }
    warshall_floyd(d);
    vector<vector<lint>> e(n, vector<lint>(n, M));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (d[i][j] <= l) {
                e[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        e[i][i] = 0;
    }
    warshall_floyd(e);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        s--, t--;
        if (e[s][t] == M) {
            cout << -1 << endl;
        } else {
            cout << e[s][t] - 1 << endl;
        }
    }
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dbg(x) cerr << #x << " : " << x << endl;
int main(){
    string s,t;
    cin >> s >> t;
    vector<ll> a[26];
    for(ll i=0;i<s.size();i++){
        a[s[i]-'a'].push_back(i);
    }
    for(ll i=0;i<26;i++){
        sort(a[i].begin(),a[i].end());
    }
    bool ok=1;
    for(ll i=0;i<t.size();i++){
        ok&=(a[t[i]-'a'].size()>=1);
    }
    if(!ok) {
        cout << -1 << endl;
        return 0;
    }
    ll len=0,prev=-1;
    vector<ll> top(26,0);
    ll n=s.size();
    for(ll i=0;i<t.size();i++){
        ll ind=t[i]-'a';
        ll req=upper_bound(a[ind].begin(),a[ind].end(),prev)-a[ind].begin();
        if(req==a[ind].size()){
            len = ceil(len*1.0/n)*n +  a[ind][0] + 1;
            prev=a[ind][0];
        } 
        else{
            len += (a[ind][req]-prev);
            prev=a[ind][req];
        }
    }
    cout << len << endl;
    return 0;
}

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

#define FOR(i,s,e) for(int i=(s);(i)<(int)(e);++(i))
#define REP(i,e) FOR(i,0,e)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define all(o) (o).begin(), (o).end()
#define psb(x) push_back(x)
#define ppb(x) pop_back(x)
#define mp make_pair
#define mt make_tuple
#define t0(t) get<0>((t))
#define t1(t) get<1>((t))
#define t2(t) get<2>((t))

typedef long long ll;

int main() {
  int h, w;
  fscanf(stdin, "%d%d ", &h, &w);
  multiset<int> hd; // horizontal distance between from start to current position
  map<int, int> hdmap; // (current column, start column) to obtain the answer in log(n)
  REP(i,w) {
    hdmap[i] = i;
    hd.insert(0);
  }
  REP(i,h) {
    int l, r;
    fscanf(stdin, "%d%d ", &l, &r);
    --l; // semiopen interval [l-1, r) based on 0-index
    auto it = hdmap.lower_bound(l);
    int re = -1;
    while (it != hdmap.end() && it->first <= r) {
      re = max(re, it->second);
      hd.erase(hd.find(it->first - it->second));
      hdmap.erase(it++);
    }
    // the only optimal start point in [l-1, r) remains
    if (re != -1 && r < w) {
      hd.insert(r-re);
      hdmap[r] = re;
    }
    int res = -1;
    if (hd.size()) res = *hd.begin() + (i+1);
    fprintf(stdout, "%d\n", res);
  }
  return 0;
}


Measured memory_bytes: 22520
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    ll a[100010];
    rep(i, N) cin >> a[i];
    
    ll sum0 = 0, sum1 = 0;
    rep(i, N) sum1 += max(0LL, a[i]);
    rep(i, K) {
        sum1 -= max(0LL, a[i]);
        sum0 += a[i];
    }
    ll ans = sum1 + max(0LL, sum0);
    //cerr << sum0 << " " << sum1 << endl;
    rep(i, N - K) {
        sum1 = sum1 + max(0LL, a[i]) - max(0LL, a[K + i]);
        sum0 = sum0 - a[i] + a[K + i];
        ans = max(ans, max(0LL, sum0) + sum1);
        //cerr << sum0 << " " << sum1 << endl;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4380
from itertools import combinations
from collections import defaultdict
from copy import deepcopy
H,W,K = map(int,input().split())

M = list(list(input()) for _ in range(H))
way = defaultdict()
ans = 0

for i in range(H+1):
    for j in range(W+1):
        for x in combinations(range(0,H),i):
            for y in combinations(range(0,W),j):
                tmp = deepcopy(M)
                for s in x:
                    for a in range(W):
                        tmp[s][a] = "r"
                for t in y:
                    for a in range(H):
                        tmp[a][t] = "r"
                if sum(i.count("#") for i in tmp) == K:
                    ans += 1

print(ans)


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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

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

  int a, b, c;
  cin >> a >> b >> c;
  if(a == b) cout << c << endl;
  else if(a == c) cout << b << endl;
  else cout << a << endl;


  return 0;
}


Measured memory_bytes: 764
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#define ll long long
#define maxn 200005
#define re register
#define inf 1e9
#define eps 1e-10
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

void write(int x)
{
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}

string s;

int main()
{
	cin>>s;
	for(int i=0;i<s.length();i++) if(s[i]!=',') cout<<s[i]; else cout<<" ";
	return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
const double EPS = 1e-10;
const double PI  = acos(-1.0);


int main(){
	ll N,M;
	while(cin>>N>>M,N|M){
		vi D(N),P(N);
		ll total=0;
		REP(i,N){
			cin>>D[i]>>P[i];
			total+=P[i]*D[i];
		}
		vector<pii> p(N);
		REP(i,N){
			p[i]=make_pair(P[i],i);
		}
		sort(RALL(p));
		ll ans=total;
		REP(i,N){
			int ii=p[i].second;
			if(M-D[ii]>=0){
				M-=D[ii];
				ans-=P[ii]*D[ii];
			}else{
				ans-=M*P[ii];
				M=0;
			}
			if(M==0){
				break;
			}
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 1352
n = int(input())
a = list(map(int, input().split()))

ans = 1
if (0 in a):
    print(0)
    exit()

for i in a:
    ans*=i
    if ans > 1e18:
        break

if ans > 1e18:
    print(-1)
else:
    print(ans)


Measured memory_bytes: 21608
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a (n);
  multiset<int> chk;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    chk.insert (a[i]);
  }
  for (int i = 0; i < n; i++) {
    int cur = a[i];
    chk.erase (chk.lower_bound(cur));
    auto it = chk.end();
    it = prev(it);
    cout << *it << '\n';
    chk.insert(cur);
  }
  return 0;
}


Measured memory_bytes: 11776
#

import sys
input=sys.stdin.readline

def main():
    NS=(input().strip("\n"))[::-1]
    dp=[[0]*2 for i in range(len(NS))]
    # 0:おつり0 1:おつり10-d
    dp[0][0]=int(NS[0])
    dp[0][1]=10-int(NS[0])
    for i in range(1,len(NS)):
        d=int(NS[i])
        dp[i][0]=min(dp[i-1][0]+d,dp[i-1][1]+d+1)
        dp[i][1]=min(dp[i-1][0]+10-d,dp[i-1][1]-1+10-d)
    dp[-1][1]+=1
    print(min(dp[-1]))
    
if __name__=="__main__":
    main()


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

using namespace std;

#define PI          3.1415926535897932384626433832795l

#define pb push_back
#define mp make_pair
#define lb lower_bound // First element which is not less than val
#define ub upper_bound // First element greater than val
#define f first
#define s second

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using vpii = vector<pair<int,int>>;
using vpll = vector<pair<ll,ll>>;

using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define endl '\n'
#define re return

#define rep(i,a,b) for (ll i = (a); i < (b); i++)
#define repz(i, a) for (ll i = 0; i < (a); i++)
#define repd(i,a,b) for (ll i = (a); i >= b; i--)
#define repdz(i,a) for (ll i = a; i >=0; i--)
#define trav(a, x) for (auto& a : x)

#define vecin(n,v) for(ll i = 0; i < n; i++) cin>>v[i];
#define llin(a) ll a; cin>>a;
#define llin2(a,b) ll a,b; cin >>a>>b;
#define llin3(a,b,c) ll a,b,c; cin>>a>>b>>c;
#define full(v) v.begin(),v.end()

void solve()
{
    int n, k;
    cin >> n >> k;
    vi h(n),dp(n);
    vecin(n,h);
    dp[0]=0;
    for(int i = 1; i < n; i++)
    {
        dp[i]=INT_MAX;
        for (int j = 1; j <= min(i,k); j++)
        {
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
        }
    }

    cout << dp[n-1] << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    //llin(t);
    //while (t--)
    //{
        solve();
    //}
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int N,num_query;
vector<int> V;

int main(){

	scanf("%d",&N);

	int tmp;
	for(int i = 0; i < N; i++){

		scanf("%d",&tmp);
		V.push_back(tmp);
	}

	scanf("%d",&num_query);

	int b,e,t;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d %d %d",&b,&e,&t);

		swap_ranges(V.begin()+b,V.begin()+e,V.begin()+t);
	}

	printf("%d",V[0]);

	for(int i = 1; i < V.size(); i++){

		printf(" %d",V[i]);
	}
	printf("\n");

	return 0;
}



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

int main() {
    string S,T,U;
    int A,B;
    cin >> S >> T;
    cin >> A >> B;
    cin >> U;

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

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
ll INF = (1LL << 31) - 1;
int MOD = 1e9+7;
ll N, M, V, P;
vector<ll> A;

bool judge2(ll x, ll target){
    vector<ll> vec = A;
    ll num = x + A[target];
    ll rem = x * (V - P);
    ll cnt = 0;
    rep(i,P-1,N){
        if(i == target)continue;
        if(A[i] > num)return false;
        cnt += min(num - A[i], x);
    }
    //cout << x << ":" << cnt << endl;
    return rem <= cnt;
}
bool judge(ll x){
    if((x+1) <= P)return true;
    if(P >= V){
        ll num = A[P-1] - A[x];
        return M >= num;
    }
    //vec.clear();
    //rep(i,P-1,N)vec.push_back(A[i]);
    ll ok = INF, ng = -1;
    while(abs(ok - ng) > 1){
        ll mid = (ok + ng) / 2;
        if(judge2(mid, x)){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    //cerr << x << "," << ok << endl;
    return M >= ok;
}
main(){
    
    cin >> N >> M >> V >> P;
    A.resize(N);
    rep(i,0,N)cin >> A[i];
    sort(A.rbegin(), A.rend());
    ll ok = 0, ng = N;
    //i問目を正解にできるか
    while(abs(ok - ng) > 1){
        ll mid = (ok + ng) / 2;
        if(judge(mid)){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    cout << ok + 1 << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using VI=vector<ll>;
using VD=vector<ld>;
using VVI=vector<VI>;
using VC=vector<char>;
using VVC=vector<VC>;
using VS=vector<string>;
using PLL =pair<ll,ll>;
using PLD=pair<ld,ld>;
using VPLL=vector<PLL>;
#define print(x) std::cout<<x<<"\n"
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repd(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SZ(x) ((ll)(x).size())
#define MAX(x) *max_element((x).begin(),(x).end())
#define MIN(x) *min_element((x).begin(),(x).end())
#define SORTR(x) sort((x).rbegin(),(x).rend())
#define SORT(x) sort((x).begin(),(x).end())
#define SUM(x) accumulate((x).begin(),(x).end(), 0)
#define FILL(x,a) fill(x.begin(),x.end(),a)
#define EACH(i,x) for(typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

const ll INF = 1e18;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;
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 (b<a) { a=b; return 1; } return 0; }
template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last){reverse(middle, last); return next_permutation(first , last);}
ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll GCD(VI v){ll a = v[0]; for (ll i = 1; i<SZ(v); i++) {a = gcd(a, v[i]);} return a;}
ll LCM(VI v){ll a = v[0]; for (ll i = 1; i<SZ(v); i++) {a = lcm(a, v[i]);} return a;}
VI Bit2Vector(const ll bit, ll n) {	VI s;	rep(i,n) if (bit & (1 << i)) s.push_back(i); return s;}


void Main()
{
	ll n,m,l; ll res=0;
	string s,t,u; string sres="No or NO";

	cin>>n;
	n=n%10;
	if(n==3) sres="bon";
	else if(n==0||n==1||n==6||n==8) sres="pon";
	else sres="hon";


	cout << sres << "\n";
	return;
}

int main()
{
	std::cin.tie(0);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }
template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	os << v[0];
	for (int i = 1; i < v.size(); i++) os << " " << v[i];
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}


void Main() {
	int N, S; cin >> N >> S;
	vvll dp(N+1, vll(S+1, 0));

	dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		int A; cin >> A;
		for (int j = 0; j <= S; j++) {
			(dp[i+1][j] += 2*dp[i][j]) %= mod2;
			if (j + A <= S) {
				(dp[i+1][j+A] += dp[i][j]) %= mod2;
			}
		}
	}

	cout << dp[N][S] << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 73656
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rRep(i,a,b) for(int i = a; i >= b; i--)
#define rrep(i,a) rRep(i,a,0)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9+7;
const ll infll = 1 << 60;
const ll mod = 1e9 + 7;

// 型による変数のオーバーフローに気をつけろ！！
// 悩んだら図やグラフを書け！！悩む前から書け！！

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

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

	ll sum = 0;
	rep(i, n) {
		sum += a[i] - 1;
	}

	cout << sum << endl;

	//最大値か
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lol long long
using namespace std;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,h,w;
  cin >>n>>h>>w;
  int ans=0;
  for(int i=0;i<n;i++){
    int a,b;
    cin >>a>>b;
    if(h<=a&&w<=b) ans++;
  }
  cout <<ans<<'\n';
  return (0);
}

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

int main(){
  int n,k; cin>>n>>k;
  vector<int> num(n);
  for(int i=0;i<n;i++){
    cin>>num[i];
  }int ans=1000000003;
  sort(num.begin(),num.end());
  for(int i=0;i<=n-k;i++){
    int x=num[i+k-1]-num[i];
    ans=min(ans,x);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (int i = int(s); i < int(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

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

int main(){
    string s; cin >> s;
    int n = s.length();
    vector<bool> data(26,false);
    rep(i,n) data[s[i]-'a'] = true;
    
    bool count = true;
    rep(i,26){
        if(data[i] == false){
            string ans = s + (char)('a' + i);
            cout << ans << endl;
            return 0;
        }
    }
    if(s == "zyxwvutsrqponmlkjihgfedcba"){
        cout << -1 << endl;
        return 0;
    }
    else{
        string save = s;
        next_permutation(s.begin(),s.end());
        string ans = " ";
        rep(i,26){
            if(save[i]==s[i]) ans += s[i];
            else { ans += s[i]; break; }
        }
        cout << ans << endl;
        return 0;
    }
}

Measured memory_bytes: 3580
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K ;
//    vector<int> a(N); int M;
//    for (int i = 0; i < N; ++i) {
//        int b;
//        cin >> b;
//        if(b == 1) {
//            a[i] = 1;
//            M = i;
//        }
//        else a[i] = 2;
//    }
//    int m = INT_MAX;
//    for (int l = 0; l < K; ++l) {
//        int r = min(N-1, M + K);
//        int ans =0;
//        if((N - r) % (K-1) == 0) ans += (N - r) / (K-1);
//        else ans += (N - r) / (K-1) + 1;
//
//        int L = max(M - l,0);
//        if(L % (K-1) == 0) ans += L / (K-1) ;
//        else ans += L / (K-1) +1;
//        m = min(ans, m);
//    }
//    cout << m << endl;
    int m = 1;
    N -= K;
    if(N % (K-1) == 0) m += N / (K-1);
    else m += N / (K-1) + 1;
    cout << m << endl;

    return 0;
}


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

int main() {
  string line;
  cin >> line;
  int n = line.size();
  vector<int> s(n);
  rep(i,0,n) {
    s[i] = stoi(line.substr(i,1));
  }
  int a = 0,b = 0;
  int c = 0,d = 1;
  rep(i,0,n) {
    if (s[i] != c) a++;
    if (s[i] != d) b++;
    c ^= 1; d ^= 1;
  }
  cout << min(a,b) << endl;
  return 0;
}


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

int main() {
  char a[4];
  scanf("%s",a);
  for(int i=0;i<3;i++){
  	if(a[i]=='1') a[i]='9';
    else a[i]='1';
  }
  printf("%s",a);
  return 0;
}


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

using namespace std;

int main() {
    int a, b, d, r;
    double f;
    cin >> a >> b;
    d = a / b;
    r = a % b;
    f = (double) a / (double) b;
    cout << d << " " << r << " " << fixed << setprecision(8) << f << endl;

    return 0;
}

Measured memory_bytes: 3280
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    class A_164_SheepAndWolves
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数配列の入力
            var Array = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

            Console.WriteLine(Array[0] <= Array[1] ? "unsafe" : "safe");

            Console.Out.Flush();
        }
    }
}


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

int main()
{
  // double x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
  double x1, y1, x2, y2;
  scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
  // cout << sqrtl((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1)) << endl;
  // cout << sqrtl((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1)) << endl;
  printf("%lf\n", hypot(x1-x2,y1-y2));
  return 0;
}


Measured memory_bytes: 3280
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s;
		int J[], O[], I[];
		
		s = sc.next();
		J = new int[s.length()];
		O = new int[s.length()];
		I = new int[s.length()];
		
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == 'J') {
				if (i == 0) {
					J[0] = 1;
				} else {
					J[i] = J[i - 1] + 1;
				}
			} else if (s.charAt(i) == 'O') {
				if (i == 0) {
					O[0] = 1;
				} else {
					O[i] = O[i - 1] + 1;
				}
			} else if (s.charAt(i) == 'I') {
				if (i == 0) {
					I[0] = 1;
				} else {
					I[i] = I[i - 1] + 1;
				}
			}
		}
		
		int max = 0;
		for (int i = s.length() - 1; 0 <= i; i--) {
			if (0 < I[i]) {
				int k = I[i];
				if (0 <= i - k - k && O[i - k] == k && k <= J[i - k - k]) {
					max = Math.max(max, k);
				}
			}
		}
		System.out.println(max);
	}
}

Measured memory_bytes: 42720
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  string s,t;
  cin >> s >> t;
  t += s;
  cout << t << "\n";
  return 0;
}


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

int main(){

 int N, K;
 cin >> N >> K;
 
 int num = 1;
  
 for(int i = 0; i < N; i++){
  if(num > K){
   num += K;
  }
  
  else{
   num *= 2;
  }
 }
 
 cout << num << endl; 
}

Measured memory_bytes: 3644
//Link : https://codeforces.com/contest/1253

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 5005
#define M 205
/*
#include <limits.h>
INT_MAX
LLONG_MAX
*/

ll seg[N*4],lazy[N*4];
int dist[N];

void push(int pos,int l,int r) {
  if(lazy[pos]!=0) {
    seg[pos] += lazy[pos];
    if(l!=r) {
      lazy[pos*2] += lazy[pos];
      lazy[pos*2+1] += lazy[pos];
    }
    lazy[pos] = 0;
  }
}
void update(int pos,int l,int r,int ql,int qr,ll val) {
  push(pos,l,r);
  if(r<ql || qr<l) {
    return;
  }
  if(ql<=l && r<=qr) {
    lazy[pos] = val;
    push(pos,l,r);
    return;
  }
  int mid = (l+r)/2;
  update(pos*2,l,mid,ql,qr,val);
  update(pos*2+1,mid+1,r,ql,qr,val);
  seg[pos] = max(seg[pos*2],seg[pos*2+1]);
}

ll query(int pos,int l,int r,int ql,int qr) {
  push(pos,l,r);
  if(r<ql || qr<l) {
    return LLONG_MIN;
  }
  if(ql<=l && r<=qr) {
    return seg[pos];
  }
  int mid = (l+r)/2;
  return max(query(pos*2,l,mid,ql,qr), query(pos*2+1,mid+1,r,ql,qr));
}

vector<pair<int,int> > q[N];

int B[N][M];
void solve() {
  int n,m;
  scanf("%d %d ", &n,&m);
  for(int i=1;i<=n-1;++i) {
    scanf("%d ", &dist[i]);
  }

  for(int i=1;i<=n;++i) {
    for(int j=1;j<=m;++j) {
      scanf("%d ", &B[i][j]);
    }
  }
  for(int i=1;i<=m;++i) {
    q[i].push_back({INT_MAX,0});
  }
  ll ret = 0;
  for(int i=1;i<=n;++i) {
    if(i-1>=1) {
      update(1,1,n,1,i-1,-dist[i-1]);
    }
    for(int j=1;j<=m;++j) {
      while(true) {
        if(q[j].back().first<=B[i][j]) {
          pair<int,int> top = q[j].back();
          q[j].pop_back();
          int ind = q[j].back().second;
          update(1,1,n,ind+1,top.second,-top.first);
        } else {
          break;
        }
      }
      int ind = q[j].back().second;
      q[j].push_back(make_pair(B[i][j],i));
      update(1,1,n,ind+1,i,B[i][j]);
    }
    ret = max(ret, query(1,1,n,1,i));
  }
  printf("%lld\n", ret);
}

int main() {
    //freopen("input.txt","r",stdin);
    solve();
    return 0;
}


Measured memory_bytes: 4736
import sys
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
cnt = [[0 for _ in range(20)] for _ in range(20)]
ans = 0
for _ in range(n):
	a = input()
	x, y = 0, 0
	if "." in a:
		i = len(a)-1
		while a[i] != ".":
			i -= 1
			x, y = x-1, y-1
		b = int(a[:i] + a[i+1:])
	else:
		b = int(a)
	#print(b)
	while b%2 == 0 and x < 9:
		x += 1
		b //= 2
	while b%5 == 0 and y < 9:
		y += 1
		b //= 5
	#print(x, y)
	x, y = x+9, y+9
	for i in range(18-x, 20):
		for j in range(18-y, 20):
			ans += cnt[i][j]
	cnt[x][y] += 1
print(ans)

Measured memory_bytes: 69232
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

ll c[222222];
vector<vector<ll> > v(222222);
ll ans[222222];
ll tmp[222222];
ll sz[222222];

void dfs(int node, int pre){
	ll color = c[node];
	ll tmp_color = tmp[color];
	REP(i, v[node].size()){
		if(v[node][i] == pre)continue;
		tmp[color] = 0;

		dfs(v[node][i], node);
		ll now = sz[v[node][i]] - tmp[color];
		sz[node] += sz[v[node][i]];
		ans[color] += now + now * (now - 1) / 2;
	}
	sz[node]++;
	tmp[color] = tmp_color + sz[node];
}

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

	ll n;cin >> n;
	REP(i, n)cin >> c[i], c[i]--;
	REP(i, n-1){
		ll a, b;cin >> a >> b;
		a--;b--;
		v[a].PB(b);
		v[b].PB(a);
	}

	dfs(n/2, -1);
	REP(i, n){
		ll now = n - tmp[i];
		ans[i] += now + now * (now - 1) / 2;
		cout << n + n * (n - 1) / 2 - ans[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 26680
package main

import (
	"fmt"
	"math"
)

func main() {
	var a, b, H, M int
	fmt.Scanf("%d %d %d %d\n", &a, &b, &H, &M)
	sin1, cos1 := math.Sincos(2 * math.Pi * (float64(H)/12.0 + float64(M)/60.0/12.0))
	sin2, cos2 := math.Sincos(2 * math.Pi * float64(M) / 60.0)
	A, B := float64(a), float64(b)
	r := math.Sqrt((A*cos1-B*cos2)*(A*cos1-B*cos2) + (A*sin1-B*sin2)*(A*sin1-B*sin2))
	fmt.Println(r)
}


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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())
#define pqasc priority_queue<long long, vector<long long>, greater<long long>>

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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

class UnionFind{
private:
  vector<int> Parent; 
 public:
  UnionFind(int N){
    Parent = vector<int>(N, -1);
  }
  
  int root(int A){
    if(Parent[A] < 0) return A;
    return Parent[A] = root(Parent[A]);
  }
  
  int size(int A){
    return -Parent[root(A)]; 
  }
  
  bool connect(int A, int B){
    A = root(A);
    B = root(B);
    if(A == B){
      return false;
    }
    if(size(A) < size(B)) swap(A, B);
    Parent[A] += Parent[B];
    Parent[B] = A;
    return true;
  }
  
  bool isSame(int A, int B){
    return root(A) == root(B);
  }
};

long long gcd(long long a, long long b) { return b ? gcd(b, a%b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }

long long ngcd(vector<long long> a) {
  long long res = a[0];
  for(int i=1; i<a.size() && res!=1; i++) res = gcd(a[i], res);
  return res;
}

long long nlcm(vector<long long> a){
  long long res = a[0];
  for(int i=1; i<a.size(); i++) res = lcm(a[i], res);
  return res;
}

bool is_prime(long long n) {
  if(n < 2) return false;
  for (long long i = 2; i * i <= n; i++) if (n % i == 0) return false;
  return true;
}

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

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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  int x; cin>>x;
  while(!is_prime(x)) x++;
  cout<<x<<endl;
}

Measured memory_bytes: 256
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()
s = 0
for e in str(n):
    s += int(e)
if n%s == 0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3436
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

const ll MXN=100000,MXM=100000;
vl G[MXN+MXM];
vl B(MXN+MXM,0);

void dfs(ll x){
  B[x]=1;
  ll k=G[x].size();
  rep(i,k){
    if(B[G[x][i]]==1){
      continue;
    }
    else{
      dfs(G[x][i]);
    }
  }
}

int main() {
  ll n,m;
  cin >> n >> m;
  rep(i,n){
    ll k;
    cin >> k;
    rep(j,k){
      ll L;
      cin >> L;
      G[i].push_back(n+L-1);
      G[n+L-1].push_back(i);
    }
  }
  dfs(0);
  rep(i,n){
    if(B[i]==0){
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
}

Measured memory_bytes: 10752
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vvll vector<vll>
#define all(v) v.begin(),v.end()
#define itr(r,v) for(auto r=v.begin();r!=v.end();r++)
#define FOR(i,n) for(ll i=0;i<n;i++)
#define ffo(i,a,b) for(ll i=a;i<=b;i++)
#define rfr(i,a,b) for(ll i=a;i>=b;i--)
#define space cout<<"\n\n";
#define endl "\n"
#define pqmx priority_queue<ll>
#define pqmn priority_queue<ll,vll,greater<ll>>
#define fps(x,y) fixed<<setprecision(y)<<x
#define merg(a,b,c) set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()))
#define set_ar(arr,v) memset(arr,v,sizeof(arr))
#define ctime auto sttart = high_resolution_clock::now()
#define etime auto sttop = high_resolution_clock::now()
#define go_t ll testcases; cin>>testcases; for(ll caseno= 1 ;caseno <= testcases; caseno++)
#define ptime auto z1z = duration_cast<microseconds>(sttop-sttart); cout<<"\nTime taken : "<<z1z.count()<<" microseconds\n"
#define dbg1(x)             cout <<#x<<": "<<x<<'\n';
#define dbg2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<'\n';
#define dbg3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<'\n';
#define dbg4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<'\n';
#define dbg5(a, b, c, d, e) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<'\n';

using namespace std;
using namespace std::chrono;

const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5;
const ll maxN = 21 + 5;
const ll MAX_SIZE = 2e6 + 6;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const double PI = 3.14159265359;

ll powerM(ll x, ll y, ll M = MOD) { // default argument
	ll v = 1; x = x % M; while (y > 0) {if (y & 1)v = (v * x) % M; y = y >> 1; x = (x * x) % M;} return v;
}

ll power(ll x, ll y) {
	ll v = 1; while (y > 0) {if (y & 1)v = v * x; y = y >> 1; x = x * x;} return v;
}

int n;
int a[maxN][maxN];
int dp[23][1 << 21]; // we need only 1<<21 as in 1<<x we have x+1 digits

// in mask -> set bit will represent that the woman hasn't found any particular match

int solve(int idx, int mask) {
	if (idx == n) {
		if (mask == 0) //  means all the women have been paired up with different men
			return 1;
		else
			return 0;
	}
	if (dp[idx][mask] != -1)
		return dp[idx][mask];
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (a[idx][i] == 1 && (mask & (1 << i))) {
			ans += solve(idx + 1, mask ^ (1 << i));
			if (ans > MOD) ans -= MOD;
		}
	}
	return dp[idx][mask] = ans;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	FIO
	memset(dp, -1, sizeof(dp));
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			cin >> a[i][j];
	}
	cout << solve(0, (1 << n) - 1);
	return 0;
}


Measured memory_bytes: 191996
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

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

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

  sort(a.begin(), a.end(), greater<ll>());

  ll ans = a[0];

  reps1(i, n-1) ans += a[(i+1)/2];

  cout << ans << endl;

  return 0;
}


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

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


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

	if (A >= B) co("delicious");
	else if (X >= B - A) co("safe");
	else co("dangerous");

	Would you please return 0;
}

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

const int MOD = 1000000007;

template <uint64_t Modulus> 
class modint {
    using u64 = uint64_t;

public:
    u64 a;

    constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
    constexpr u64 &value() noexcept { return a; }
    constexpr const u64 &value() const noexcept { return a; }
    constexpr modint operator+(const modint rhs) const noexcept {
        return modint(*this) += rhs;
    }
    constexpr modint operator-(const modint rhs) const noexcept {
        return modint(*this) -= rhs;
    }
    constexpr modint operator*(const modint rhs) const noexcept {
        return modint(*this) *= rhs;
    }
    constexpr modint operator/(const modint rhs) const noexcept {
        return modint(*this) /= rhs;
    }
    constexpr modint &operator+=(const modint rhs) noexcept {
        a += rhs.a;
        if (a >= Modulus) {
        a -= Modulus;
        }
        return *this;
    }
    constexpr modint &operator-=(const modint rhs) noexcept {
        if (a < rhs.a) {
        a += Modulus;
        }
        a -= rhs.a;
        return *this;
    }
    constexpr modint &operator*=(const modint rhs) noexcept {
        a = a * rhs.a % Modulus;
        return *this;
    }
    constexpr modint &operator/=(modint rhs) noexcept {
        u64 exp = Modulus - 2;
        while (exp) {
        if (exp % 2) {
            *this *= rhs;
        }
        rhs *= rhs;
        exp /= 2;
        }
        return *this;
    }
    friend ostream &operator<<(ostream &os, const modint<Modulus> &i) {
        os << i.a;
        return os;
    }
    friend istream &operator>>(istream &is, modint<Modulus> &i) {
        is >> i.a;
        return is;
    }
};

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

    int n;
    modint<MOD> k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);        
    }

    modint<MOD> x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a.at(i) > a.at(j)) x += 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a.at(i) > a.at(j)) y += 1;
        }
    }

    modint<MOD> ans = k * x + y * (k * (k - 1) / 2);
    cout << ans << endl;
}

Measured memory_bytes: 256
h,w,k = map(int,input().split())
ls = [str(input()) for _ in range(h)]
a = [[] for _ in range(2**h)]
b = [[] for _ in range(2**w)]
for i in range(2**h):
    for j in range(h):
        if (i>>j)&1:
            a[i].append(j)
for s in range(2**w):
    for l in range(w):
        if (s>>l)&1:
            b[s].append(l)
p = 0
for e in range(2**h):
    for f in range(2**w):
        cnt = 0
        for g in range(len(ls)):
            if g not in a[e]:
                di = list(ls[g])
                for t in range(len(di)):
                    if t not in b[f]:
                        if di[t] == "#":
                            cnt += 1
        if cnt == k:
            p += 1
print(p)

Measured memory_bytes: 9152
#include<iostream>
#include<vector>
 
using namespace std;
 
class DisjointSet {
public:
    vector<int> rank, p;
 
    DisjointSet(){}
    DisjointSet(int size) {
        rank.resize(size, 0);
        p.resize(size, 0);
        for (int i = 0; i < size; i++)makeSet(i);
    }
 
    void makeSet(int x) {
        p[x] = x;
        rank[x] = 0;
    }
 
    bool same(int x, int y) {
        return findSet(x) == findSet(y);
    }
 
    void unite(int x, int y) {
        link(findSet(x), findSet(y));
    }
 
    void link(int x, int y) {
        if (rank[x] > rank[y]) {
            p[y] = x;
        }
        else {
            p[x] = y;
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
    }
 
    int findSet(int x) {
        if (x != p[x]) {
            p[x] = findSet(p[x]);
        }
        return p[x];
    }
};
 
int main() {
    int n, a, b, q;
    int t;
 
    cin >> n >> q;
    DisjointSet ds = DisjointSet(n);
 
    for (int i = 0; i < q; i++) {
        cin >> t >> a >> b;
        if (t == 0)ds.unite(a, b);
        else if (t == 1) {
            if (ds.same(a, b))cout << 1 << endl;
            else cout << 0 << endl;
        }
    }
 
    return 0;
}


Measured memory_bytes: 3180
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	while(true){
		cin >> N;
		if(N==0){return 0;}

		int* x = new int[N];
		int sum=0;

		for(int i=0; i<N; i++){
			cin >> x[i];
			sum += x[i]; 
		}
		int* x_max = max_element(x,x+N);
		int* x_min = min_element(x,x+N);

		cout << (sum - *x_max - *x_min)/(N-2) << endl;

		delete[] x;
	}
}

Measured memory_bytes: 1196
S = input()
ans = 0
for i in range(len(S)):
    j = 0
    while i+j < len(S):
        if S[i+j:i+j+1] in ('A', 'C', 'T', 'G'):
            j += 1
        else:
            break
    ans = max(ans, j)

print(ans)


Measured memory_bytes: 9068
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    ll a, b, k;
    cin >> a >> b >> k;
    if(a <= k){
        k-=a;
        a = 0;
    }
    else{
        a-=k;
        k = 0;
    }
    if(b <= k)b = 0;
    else b = b-k;
    cout << a << " " << b << endl;
}


Measured memory_bytes: 256
S = input()

#print ((len(S)-1)//2)
#print ((len(S)+3)//2)
#print (S[0:(len(S)-1)//2])
#print (S[((len(S)+3)//2)-1:len(S)])
#print (S[::-1])

Skai1 = S[0:(len(S)-1)//2]
Skai1 = Skai1[::-1]
Skai2 = S[((len(S)+3)//2)-1:len(S)]
Skai2 = Skai2[::-1]

if S==S[::-1] and S[0:(len(S)-1)//2] ==Skai1 and S[((len(S)+3)//2)-1:len(S)] == Skai2: 
  print('Yes')
else:
  print("No")

Measured memory_bytes: 9076
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

ll N;

int main() {
    cin >> N;
    ll ans = 0;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i != 0) continue;
        if (i - 1 > N / i)
            ans += i - 1;
        if (N / i == i) continue;
        if (N / i - 1 > i)
            ans += N / i - 1;
    }

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


Measured memory_bytes: 256