akhauriyash/Code-Regression huggingface dataset:
N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)

D = 40
dp = Array.new(D + 1) {
  Array.new(2, -1)
}

dp[0][1] = 0

0.upto(D-1) do |d|
  mask = 1 << D - d - 1

  num = 0
  A.each do |a|
    if a & mask > 0
      num += 1
    end
  end

  cost0 = mask * num
  cost1 = mask * (N - num)

  dp[d + 1][1] = dp[d][1] + ((K & mask > 0) ? cost1 : cost0)

  if K & mask > 0
    dp[d + 1][0] = dp[d][1] + cost0
  end

  if dp[d][0] != -1
    dp[d + 1][0] = [
      dp[d + 1][0],
      dp[d][0] + [cost0, cost1].max
    ].max
  end
end

puts [dp[D][0], dp[D][1]].max

Measured memory_bytes: 9388
number = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
 
print(number[int(input())-1])

Measured memory_bytes: 3060
#include<bits/stdc++.h>
// #include <boost/lexical_cast.hpp>
using namespace std;

#define ll long long int
#define vll vector<ll>
#define vllv vector<vector<ll>> 
#define vpii vector<pair<ll,ll>>
#define sz size()
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll MOD=1000000000+7;
ll ceil1(ll n,ll m){if(n%m==0){return n/m;}return n/m +1;}
ll factor(ll n){
    vll ans;
	if(n==2)ans.pb(2);
	else
    {for(ll i=2;i*i<=n;i++){if(n%i==0 && n%i!=i){ans.pb(i);if(n/i!=i)ans.pb(n/i);}}ans.pb(n);}
    return ans.sz+1;
}
ll fact(ll n){ll res = 1;for (ll i = 2; i <= n; i++)res = res * i; 
    return res; } 
  
ll nCr(ll n, ll r){ return fact(n) / (fact(r) * fact(n - r)); } 
  
void dfs(vllv &v,ll k,vll &par,vll &dis,ll p)
{
    par[k]=p;
    dis[k]=dis[p]+1;
    for(ll i=0;i<v[k].sz;i++){
        if(v[k][i]!=p){
            dfs(v,v[k][i],par,dis,k);
        }
    }
}
bool sortbysec(const pair<string,int> &a,const pair<string,int> &b){return (a.second<b.second);} 

ll pow2(ll n,ll k){ll ans=1;
    while(k>0){
        if(k%2==1)ans=ans*n;n=n*n;k/=2;
    }return ans;}
bool prime(int n){
    int i,j;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
bool bserch(vector<string> a, string s){
	ll l=0,r=a.sz-1,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(a[mid]==s)return true;
		if(a[mid]<s){
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	return false;
}

bool sortcol(const vector<int>& v1, 
               const vector<int>& v2){ 
 return v1[0] < v2[0]; } 

 ll sumdegit(ll n)
 {
 	ll sum=0;
 	while(n>0)
 	{
 		sum+=(n%10);
 		n/=10; 	}
 		return sum;
 }

void solve()
{
	/*ll h,w,k;
	vector<string> s;
	for(ll i=0;i<n;i++)
		cin>>s;*/
	ll n;
	cin>>n;
	vll a(n);
	for(ll i=0;i<n;i++)
		cin>>a[i];
	sort(all(a));
	ll ans=0;
	ans+=a[n-1];
	
	ll k=n-2;
	
	ll c=n-2;
	while(1)
	{
		if(c==0)
			break;
		if(c>1)
		{
			// cout<<a[k]<<" ";
			ans+=(2*a[k]);
			k--;
			c-=2;
			if(c==0)
				break;
		}
		else if(c==1)
		{
			// cout<<a[k]<<" ";
			ans+=a[k];
			k--;
			break;
		}
		
	}
	cout<<ans;
	return;
}  
int main()
{
	fast;
    ll q;
    q=1;
    // cin>>q;
    while(q--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 4748
#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(c) begin(c), end(c)
#define range(i,a,b) for(int i = a; i < (int)(b); i++)
#define rep(i,b) range(i,0,b)
#define eb emplace_back
typedef long long ll;
auto const inf = numeric_limits<ll>::max()/4;

using Weight = ll;
using Capacity = int;
struct Edge {
    int src, dst; Weight weight;
    Edge(int s, int d, int w) : src(s), dst(d), weight(w) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

pair<vector<Weight>, bool> spfa(const Graph &g, int s){
    const Weight inf = numeric_limits<Weight>::max()/4;
    const int n = g.size(); queue<int> q;
    vector<Weight> dist(n, inf); vector<int> inQ(n);
    vector<int> count(n);
    dist[s] = 0; q.emplace(s); inQ[s] = true; ++count[s];
    bool negCycle = false;
    for(int i = 0; q.size(); i++){
        int v = q.front(); q.pop(); inQ[v] = false;
        for(auto &e : g[v]){
            if(dist[v] != inf && dist[e.dst] > dist[v] + e.weight){
                dist[e.dst] = dist[v] + e.weight;
                if(!inQ[e.dst]){
                    q.emplace(e.dst); inQ[e.dst] = true; ++count[e.dst];
                    if(count[e.dst] >= n){ negCycle = true; goto END; }
                }
            }
        }
    }
 END:;
    return make_pair(dist, !negCycle);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int V,E,r;
    while(cin >> V >> E >> r){
        Graph g(V);
        rep(i,E){
            int a,b,c;
            cin >> a >> b >> c;
            g[a].eb(a,b,c);
        }
        bool ok;
        vector<Weight> dist;
        tie(dist, ok) = spfa(g,r);
        if(ok){
            for(int i = 0; i < (int)dist.size(); i++){
                if(dist[i] == inf) cout << "INF";
                else cout << dist[i];
                cout << endl;
            }
        } else {
            cout << "NEGATIVE CYCLE" << endl;
        }
    }
}

Measured memory_bytes: 19016
import sys
sys.setrecursionlimit(10**9)
N, M ,Q = map(int, input().split())
abcd = [0 for _ in range(Q)]
for i in range(Q):
    abcd[i] = list(map(int, input().split()))

ans = 0
def dfs(A):
    global ans
    if len(A) == N:
        score = 0
        for i in range(Q):
            if A[abcd[i][1]-1] - A[abcd[i][0]-1] == abcd[i][2]:
                score += abcd[i][3]
        ans = max(ans, score)
    else:
        for i in range(A[-1], M+1):
            dfs(A + [i])

for j in range(1, M+1):
    dfs([j])
    
print(ans)


Measured memory_bytes: 9164
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for _ in range(q):
    a1,b1,c1,d1=map(int,input().split())
    a.append(a1)
    b.append(b1)
    c.append(c1)
    d.append(d1)

A=[1]*(n+1)
mx=0
while A[0]==1:
    s=0
    for i in range(0,q):
        if A[b[i]]-A[a[i]]==c[i]:s+=d[i]
    mx=max(mx,s)
    k=n
    while A[k]==m and k>=1:
        k-=1
    A[k]+=1
    for i in range(k+1,n+1):
        A[i]=A[i-1]
print(mx)





Measured memory_bytes: 68104
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#include<deque>
#include <regex>
#include <list> 
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define per(i,n) for(ll i=n-1;i>=0; --i)
#define all(x) (x).begin(),(x).end()
#define _GLIBCXX_DEBUG
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; }
const long long INF = 1LL << 60;
typedef long long ll;
const ll MOD = 1000000007;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll getDigit(ll n) {
	ll cnt = 0;
	while (n != 0) {
		n /= 10;
		cnt++;
	}
	return cnt;
}
int main() {
	ll n, k;
	cin >> n >> k;
	vector<ll>h(n);
	rep(i,n)cin >> h[i];
	sort(all(h));
	reverse(all(h));
	if (k >= n)return cout << 0 << endl,0;
	cout << accumulate(h.begin() + k, h.end(), 0LL) << endl;
}

Measured memory_bytes: 1792
// Remeber Choose Compiler: GCC9
#include <bits/stdc++.h>

using namespace std;

// Debug Output Utility
#ifdef LOCAL
#define dbg(args...)             \
    do {                         \
        cout << #args << " -> "; \
        err(args);               \
    } while (0)
void err() { std::cout << std::endl; }
template <typename T, typename... Args>
void err(T a, Args... args) {
    std::cout << a << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &... args) {
    for (auto &v : arg)
        std::cout << v << ' ';
    err(args...);
}
#else
#define dbg(...)
#endif

// Macro Definitions:
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

// Type Alias:
using int64 = long long;
using PII   = pair<int, int>;

// Global Const Variable
const int64 INF  = 0x3f3f3f3f3f3f3f3f;
const int MOD  = 1000000007;
const int MAXN = 105;
const int MAXL = 1000;

int vis[MAXN];

void run() {
    int x,n,y;
    cin >> x >> n;
    for(int i=0;i<n;i++) cin >> y, vis[y] = 1;
    for(int beg=x,end=x;;beg--,end++) {
        if(!vis[beg]) { cout << beg << endl; break; }
        if(!vis[end]) { cout << end << endl; break; }
    }
    
}

// Debug Input Redirection
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    run();
}

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

int compare(const void *a, const void *b) {
    return strcmp((char*)a, (char*)b);
}


int main(void)
{
    int N, L;
    int i = 0;

    // input
    scanf("%d %d", &N, &L);

    char S[N][L + 1];

    for (i = 0; i < N; i++) {
        scanf("%s", S[i]);
    }

    qsort(S, N, L + 1, compare);

    // output
    for (i = 0; i < N; i++) {
        printf("%s", S[i]);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 252
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){
 ll a,b ;cin>>a>>b ;
 a-- ; 
 ll bd= b/2 ; ll ad= a/2 ;
 ll c= 0 ;ll d= 0 ;
 if(b%2==0){
     if((bd)%2==0) d= b ;
     else d= b^1;
      }
 else{
     if((bd+1)%2==0) d= 0 ;
     else d= 1 ;
 }
 if(a==-1) cout<<d<<endl ;
 else{
     if(a%2==0) {
         if(ad%2==0) c= a ;
         else c= a^1 ;
         }
     else{
         if((ad+1)%2==0) c=0 ;
         else c=1 ;
     }
     ll ans= c^d ;
     cout<< ans <<endl ; 
 } 

 return 0 ; 
}

Measured memory_bytes: 3604
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int main(){
    ll r,d,x;
    cin >> r >> d >> x;
    rep(i,10){
        x = r * x - d;
        cout << x << endl;
    }
}

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

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define all(v) v.begin(), v.end()

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<ll, ll>;

const ll INF = (1LL<<60);

int main(){

    ll n; cin >> n;
    if(n%2==0){
        cout << 0.5 << endl;
        return 0;
    }

    cout << (long double)(n/2+1)/(long double)n << endl;

    return 0;
}

Measured memory_bytes: 3792
n=int(input())
a=list(map(int,input().split()))
b=0
for i in range(n):
    if a[i]%2==0:
        if a[i]%3!=0 and a[i]%5!=0:
            b+=1
if b==0:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include<numeric>
#include<cmath>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> pll;
const ll inf = 1LL << 60;

int main(){
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
    int a,b;cin>>a>>b;
    cout <<a*b << endl;
}

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

using namespace std;

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

    int s_len = s.size();
    reverse(s.begin(), s.end());

    long long ans = 0;
    int x = 1;
    int sum = 0;
    vector<int> cnt(2019);
    for ( int i = 0; i < s_len; i++ ) {
        cnt.at(sum)++;
        sum += (s.at(i) - '0') * x;
        sum %= 2019;
        ans += cnt.at(sum);
        x = (10 * x) % 2019;
    }

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


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define ARRAY_LENGTH(array) sizeof(array)/sizeof(*array)
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; }

ll dp(ll h) {
    ll ans;

    if(h == 1) {
        ans = 1;
    } else {
        ans = 2*dp(h/2) + 1;
    }

    return ans;
}

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

    if(H == 1) {
        cout << 1 << endl;;
    } else {
        cout << 2*dp(H / 2) + 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 3620
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_set>

//#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif

using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pl;

#define FST first
#define SND second

#define MAX_H   (800)                  // 10^5
#define MAX_N   (100000)                  // 10^5
#define BASE    (1000000000 + 7)          // 10^9 + 7
#define INFI    (1000000000 + 7)          // 10^9 + 7
#define INFL    (1000000000000000000 + 7) // 10^18 + 7

ll H, W, K;
string MAP[MAX_H];
int DIST[MAX_H][MAX_H];

bool is_inside(int i, int j) {
  return 0 <= i && i < H && 0 <= j && j < W;
}

ll min_turn() {
  int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

  queue<Pi> que;
  vector<Pi> cell;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      DIST[i][j] = INFI;
      if (MAP[i][j] == 'S') {
        que.push(Pi(i, j));
        cell.push_back(Pi(i, j));
        DIST[i][j] = 0;
      }
    }
  }

  while (!que.empty()) {
    Pi p = que.front(); que.pop();
    int r = p.FST, c = p.SND;
    for (int i = 0; i < 4; i++) {
      int rx = r + dir[i][0], cx = c + dir[i][1];
      if (is_inside(rx, cx)) {
        int dist = DIST[r][c] + 1;
        if (MAP[rx][cx] == '.' && dist < DIST[rx][cx] && dist <= K) {
          DIST[rx][cx] = dist;
          que.push(Pi(rx, cx));
          cell.push_back(Pi(rx, cx));
        }
      }
    }
  }

  ll mn = INFI;
  for (auto p : cell) {
    int r = p.FST, c = p.SND;
    ll vals[4] = {r, c, H - 1 - r, W - 1 - c};
    for (int i = 0; i < 4; i++) mn = min(mn, vals[i]);
  }

  return (mn + 2 * K - 1) / K;
}

void solve() {
  ll ans = min_turn();
  cout << ans << endl;
}

int main() {
  cin >> H >> W >> K;

  for (int i = 0; i < H; i++) cin >> MAP[i];

  solve();

  return 0;
}

Measured memory_bytes: 13168
#include<stdio.h>
#include<ctype.h>


int main(){

  char c;

  while(1){
    scanf("%c", &c);
    if(c=='\n'){
      printf("\n");
      break;
    }else if(islower(c)!=0) printf("%c", toupper(c));
    else if(isupper(c)!=0) printf("%c", tolower(c));
    else printf("%c", c);
  }

  
  return 0;
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
 
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
 
const long double PI = acos(-1);
 
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}

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

  vector<ll> a(n+1);
  a[0] = a[1] = 1;
  for(ll i = 2; i <= n; i++){
    ll num = i;
    for(ll j = 2; j <= i; j++){
      while(num % j == 0){
        a[j]++;
        num /= j;
      }
    }
  }

  ll ans = 1;
  for(ll i = 2; i <= n; i++){
    ans *= (a[i]+1);
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  int n;
  cin >> n;
  if(n%1000==0) cout << 0 << endl;
  else cout << 1000-n%1000 << endl;;
}


Measured memory_bytes: 3644
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long int LL;
const int Max_N(100050);

int N, Head[Max_N], Total, To[Max_N << 1], Next[Max_N << 1], Weight[Max_N << 1], Size[Max_N], SonMax[Max_N], root;
LL Ans;

inline void Add_Edge(int s, int t, int w)
{
	++Total, To[Total] = t, Next[Total] = Head[s], Weight[Total] = w, Head[s] = Total;
}

void dfsSize(int u, int fa)
{
	Size[u] = 1, SonMax[u] = 0;
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
			dfsSize(v, u), Size[u] += Size[v], SonMax[u] = max(SonMax[u], Size[v]);
	SonMax[u] = max(SonMax[u], N - Size[u]);
}

void dfsDist(int u, int fa, LL Dis)
{
	Ans += Dis * 2LL;
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
			dfsDist(v, u, Dis + Weight[i]);
}

/*
考虑提出任意重心root，可以证明：存在一个最优解，使得哈密顿路上相邻两个点的路径均经过root
可以先构造出哈密顿回路：把在不同子树中的点两两匹配起来（可能存在孤立点），以root为起点，再考虑root走到的点和走到root的点，显然哈密顿回路 = Sum{2 * Dist(root, i)   |   1 <= i <= N}
然后考虑去掉哈密顿回路上边权最小的边就可以得到答案，显然一定是去掉和root相邻的一个点x到root的路径（是root走到的点或走到root的点）
当最大子树匹配过程中有孤立点时，x必须在可能存在孤立点的子树中（root走到的点或走到root的点在该子树中）：(1)最大子树 或 (2)去掉该子树中1个点，2 * 最大子树 >= 剩下的点数N - 2 
*/

int main()
{
	scanf("%d", &N);
	for (int i = 1, u, v, w;i != N;++i)
		scanf("%d%d%d", &u, &v, &w), Add_Edge(u, v, w), Add_Edge(v, u, w);
	dfsSize(1, -1), root = 1;
	for (int i = 2;i <= N;++i)
		if (SonMax[i] < SonMax[root])
			root = i;
	dfsDist(root, -1, 0LL);
	dfsSize(root, -1);
	int Min(0X3F3F3F3F);
	if (N & 1)//SonMax[root] <= N / 2，N是奇数故SonMax[root] <= (N - 1) / 2，所以可以两两匹配，不存在孤立点
		for (int i = Head[root];i;i = Next[i])
			Min = min(Min, Weight[i]);
	else//找可能存在孤立点的子树 
		for (int i = Head[root], v;i;i = Next[i])
			if (Size[v = To[i]] == SonMax[root] || (N - 2 >= 2 * SonMax[root]))
				Min = min(Min, Weight[i]);
	printf("%lld", Ans - Min);
	return 0;
}

Measured memory_bytes: 7680
// Dont hack this or I hack ur mama
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#define ll long long 
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define EPS (1e-9)
using namespace std;

////////////// END OF TEMPLATE
const int nmax = 100005;
const ll mod = 1000000007;
ll inv[nmax],fact[nmax],ifact[nmax],x[nmax];
void precompute()
{
	inv[1] = 1;
	fact[1] = 1;
	fact[0] = 1;
	ifact[0] = 1;
	ifact[1] = 1;
	x[1] = 1;

	for(int i = 2 ; i < nmax; ++i)
	{
		inv[i] = ((mod - mod/i) * inv[mod%i] )% mod;
		fact[i] = (fact[i-1] * i) % mod;
		ifact[i] = (ifact[i-1] * inv[i]) % mod;
		x[i]=x[i-1]^i;
	}
}
ll calc(int n, int m)
{
	if(m > n)
		return 0LL;
	//cout << fact[n] << ' '<< ifact[m] << ' '<< ifact[n-m] << endl;
	return (fact[n] * (ifact[m] * ifact[n-m] % mod)) % mod;
}
int n;
int a[nmax];
void read()
{
	precompute();
	//ut << calc(32,5) << endl;
	cin >> n;
	for(int i = 0; i <= n; ++i)
	{
		cin >> a[i];
		x[n] ^= a[i];

	}
	vector < int > v;
	for(int i = 0 ; i<=n;++i)
		if(a[i] == x[n])
			v.push_back(i);
	int d = v[1]-v[0];
	cout << n << endl;
	for(int i = 2; i<=n+1; ++i)
		//cout << calc(n+1,i) << ' ' << calc(n-d,i-1) << ' ' << (calc(n+1,i) - calc(n-d,i-1) + mod) %mod << endl; 
	cout << (calc(n+1,i) - calc(n-d,i-1) + mod)%mod << endl;
}
void solve()
{
	
}
int main()
{
	std::ios::sync_with_stdio(false);
	read();
	solve();
	return 0;
}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define dame {cout<< "-1" <<"\n"; return;}
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
#define PI (acos(-1))
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------
struct edge{ll to;};
struct graph{
    ll N;
    vector<vector<edge> > G;
    vector<vector<ll>> Gr;
    vector<ll> indegree; //各ノードの入次数
    queue<ll> noindegree; //入次数0のノード
    vector<ll> topo; //topoligical sorted

    graph(ll n): N(n), G(N), Gr(N), indegree(N){}
    
    void add_edge(ll s, ll t){
        G[s].emplace_back((edge){t});
        Gr[t].emplace_back(s);
        ++indegree[t];
    }

    void go(){
        rep(i,N) if(indegree[i]==0) noindegree.emplace(i);
        while(!noindegree.empty()){
            ll v=noindegree.front();
            noindegree.pop();
            topo.emplace_back(v);
            for(auto E: G[v]){
                if(--indegree[E.to]==0) noindegree.push(E.to);
            }
        }
    }

};


//--MAIN-----------------------------------
void Main() {
    ll N,M; cin>>N>>M;
    graph g(N);
    vector<ll> A(N-1+M);
    vector<ll> B(N-1+M);
    rep(i,N-1+M){
        cin>>A[i]>>B[i]; --A[i],--B[i];
        g.add_edge(A[i],B[i]);
    }
    g.go();
    vector<ll> parent(N,-1);
    rep(i,N){
        ll v=g.topo[i];
        for(auto E: g.G[v]){
            parent[E.to]=v;
        }
    }
    rep(i,N){
        cout<< parent[i]+1 <<"\n";
    }

}
//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 15864
#include <iostream>
#include <string>
int main() {
	std::string a;

	int Q = 0;
	int N = 0;
	int left, right;
	int result[99999] = { 0, };

	std::cin >> N >> Q >> a;

	if (a[0] == 'A'&&a[1] == 'C') result[0]++;

	for (int j = 1; j < N; j++) {
		result[j] += result[j - 1];
		if (a[j] == 'A'&&a[j + 1] == 'C') result[j]++;
	}


	for (int i = 0; i < Q; i++) {
		std::cin >> left >> right;
		right = result[right - 2]- result[left - 1];
		if (a[left - 1] == 'A'&&a[left] == 'C') right++;
	
		std::cout << right << std::endl;
	}

	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <iomanip>
#define M 100000
#define MAX 1000000001
#define MIN -100000000
#define mod 998244353 
#define ss second
#define ff first
#define ll long long int
#define pb push_back
#define ld double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;

int main(){
	int x,y;
	cin>>x>>y;
	int b2 = y-2*x;
	int a2 = 4*x-y;
	if(b2>=0 && b2%2 == 0 && a2>=0 && a2%2 == 0){
		cout<<"Yes\n";
	}
	else
		cout<<"No\n";
	return 0;
}

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

#define REP(i,n) for(int i=0; i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VC vector<char>
#define FOREACH(x,a) for(auto& (x) : (a) )
using namespace std;

int main() {
	int a, b, k;
	cin >> a >> b >> k;
	if (2 * k - 1 >= b - a) {
		for (int i = a; i <= b; i++) {
			cout << i << endl;
		}
	}
	else {
		for (int i = a; i < a + k; i++) {
			cout << i << endl;
		}
		for (int i = b - k + 1; i <= b; i++) {
			cout << i << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))

start = 0
for i in range(N):
    if A[i] == 1:
        start = i
        break

ans = N
for i in range(K):
    cnt = 1
    left = start + 1 - K + i
    if left > 0:
        if left % (K - 1) != 0: cnt += 1
        cnt += left // (K - 1)

    raight = N -1 - start - i
    if raight > 0:
        if raight % (K - 1) != 0: cnt += 1
        cnt += raight // (K - 1)
    ans = min(ans, cnt)

print(ans)

Measured memory_bytes: 14008
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


N, Y = map(int, input().split())
X = list(map(int, input().split()))

X.append(Y)
X2 =sorted(X)
X3 = []

for i in range(1, len(X)):
    X3.append(X2[i] - X2[i-1])

print(gcd_list(X3))


Measured memory_bytes: 20332
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

s = input().strip()
if s[-1] != 's':
    s+='s'
else:
    s += 'es'
print(s)

Measured memory_bytes: 61644
import java.util.Scanner;

public class Main {
	
	private static final long MOD = 1000000000 + 7;
	
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)) {
			
			int n = sc.nextInt();
			
			long[] dp0 = new long[n+1];
			long[] dp9 = new long[n+1];
			long[] dpNone = new long[n+1];
			long[] dp19 = new long[n+1];
			
			dp0[1] = 1;
			dp9[1] = 1;
			dpNone[1] = 8;
			dp19[1] = 0;
			
			for(int i = 2 ; i <= n ; i++ ) {
				dp0[i] = add(mult(dp0[i-1],9), dpNone[i-1]);
				dp9[i] = add(mult(dp9[i-1],9), dpNone[i-1]);
				dpNone[i] = mult(dpNone[i-1], 8);
				dp19[i] = (mult(dp19[i-1], 10) + dp0[i-1] + dp9[i-1]) % MOD;
			}
			
			System.out.println(dp19[n]);
		}
	}
	
	public static long mult(long a, long b) {
		return (a * b) % MOD; 
	}
	
	public static long add(long a, long b) {
		return (a + b) % MOD;
	}

}

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

#define int long long
#define fast_io(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(x) x.begin(),x.end()
#define us unordered_set
#define um unordered_map
#define ms multiset
#define mm multimap
#define pb push_back
#define pf push_front
#define ins insert
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define _max max_element
#define _min min_element
#define tc(T) int T; cin>>T; while(T--)
#define q(q) int q; cin>>q; while(q--)
#define pi 3.1415926535897932384626433832
const int pinf=((int)2e18);
const int ninf=((int)-2e18);
const int mod=1000000007;

using namespace std;

int32_t main()
{
    fast_io();

    //FILE *fptr1=freopen("../in.txt","r",stdin);
    //FILE *fptr2=freopen("out.txt","w",stdout);


    int n;
    cin>>n;
    
    cout<<3LL*n*n;


    return 0;
}


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

#define SIZE 300005

int N;		/* 2 ~ 3E5 */
char S[SIZE];
int resistor=0;
int min=0;

int main(){
#ifdef DEBUG
	printf("DEBUGGING ON\n");
#endif
	scanf("%d",&N);
	scanf("%s",S);
	for (int i=1;i<N;++i){
		if(S[i]=='E')resistor+=1;
	}		/* The number of change if the leader was the zeroth man */
	min=resistor;
	int prechange=0,mychange=0;
	for (int i=1; i<N;++i){
		prechange=(S[i-1]=='W')?1:0;
		mychange=(S[i]=='E')?-1:0;
		resistor+=prechange+mychange;
		if (resistor<min) min = resistor;
	}
	printf("%d\n",min);
	return (0);
}

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

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

using ll = long long;

const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

int main() {
  int A,B;
  cin>>A>>B;
  int S = max(A,B),T=min(A,B);
  vector<vector<int>> ans(100,vector<int>(100,0));
  int cnt = 0;
  int lastx,lasty;
  if(T!=1){
    for(int i = 1; i <= 98;i=i+4){
      for(int j = 1; j <= 98; j = j+4){
        for(int k = 0; k < 8; k++) {
          ans[i+dx[k]][j+dy[k]]=1;
        }
        cnt++;
        if(cnt>=T-1) {
          lastx=i;
          lasty=j;
          break;
        }
      }
      if(cnt>=T-1) break;
    }
  }
  int rest = 0;
  for(int i = lastx+3; i < 100; i=i+2){
    for(int j = 0; j < 100; j=j+2){
      ans[i][j]=1;
      rest++;
      if(rest>=S-T+1) break;
    }
    if(rest>=S-T+1) break;
  }
  cout<<100<<" "<<100<<endl;
  if(A>B) {
    for(int i = 0; i < 100; i++){
      for(int j = 0; j < 100; j++){
        if(ans[i][j]==0) cout<<'#';
        if(ans[i][j]==1) cout<<'.';
      }
      cout<<endl;
    }
  }
  else{
    for(int i = 0; i < 100; i++){
      for(int j = 0; j < 100; j++){
        if(ans[i][j]==0) cout<<'.';
        if(ans[i][j]==1) cout<<'#';
      }
      cout<<endl;
    }
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<stdlib.h>


struct Node {
	int key;
	Node *next, *prev;
};

Node *nil;

Node* listSearch(int key) {
	Node *cur = nil->next;
	while (cur != nil && cur->key != key) {
		cur = cur->next;
	}
	return cur;
}

void init() {
	nil = (Node *)malloc(sizeof(Node));
	nil->next = nil;
	nil->prev = nil;
}

void printList() {
	Node *cur = nil->next;
	int isf = 0;
	while (1) {
		if (cur == nil)break;
		if (isf++ > 0)printf(" ");
		printf("%d", cur->key);
		cur = cur->next;
	}
	printf("\n");
}

void deleteNode(Node *t) {
	if (t == nil)return;
	t->prev->next = t->next;
	t->next->prev = t->prev;
	free(t);
}

void deleteFirst() {
	deleteNode(nil->next);
}

void deleteLast() {
	deleteNode(nil->prev);
}

void deleteKey(int key) {
	deleteNode(listSearch(key));
}

void insert(int key) {
	Node *x = (Node *)malloc(sizeof(Node));
	x->key = key;
	x->next = nil->next;
	nil->next->prev = x;
	nil->next = x;
	x->prev = nil;
}

int main() {
	int key, n, i;
	int size = 0;
	char com[20];
	int np = 0, nd = 0;
	scanf("%d", &n);
	init();
	for (i = 0; i < n; i++) {
		scanf("%s", com);
		if (strlen(com) <= 6) {
			scanf("%d", &key);
		}
		if (com[0] == 'i') {
			insert(key);
			np++; size++;
		}
		else if (com[0] == 'd') {
			if (strlen(com) > 6) {
				if (com[6] == 'F')deleteFirst();
				else if (com[6] == 'L')deleteLast();
			}
			else { deleteKey(key); nd++; }
			size--;
		}
	}

	printList();

		return 0;
}



Measured memory_bytes: 33940
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 1e6 * 2 + 10, INF = 1e9 * 1e9 + 10, M = 1e9 * 1e8;



int main()
{
    fastInp;

    ll n;
    cin >> n;
    n++;
    vector<ll> vec(n);

    for (int i = 0; i < n; i++) cin >> vec[i];
    
    ll ans = 0, pw = 1;

    vector<ll> lft;
    for (int i = 0; i < n; i++) {
        lft.push_back(pw);
        if (vec[i] > pw) {
            cout << "-1";
            return 0;
        }
        ll vl = 0;
        ans += vec[i];
        pw -= vec[i];
        
        if (pw <= M) {
            pw *= 2;
        }
    }

    ll curMax = 0;
    for (int i = n - 1; i > 0; i--) {
        curMax = curMax + vec[i];

        if (lft[i] / 2 <= curMax) {
            ans += lft[i] / 2;
        } else {
            ans += curMax;
        }
    }

    cout << ans;
    return 0;
}

Measured memory_bytes: 5056
//------------------------------>> tsukasa_diary's template <<------------------------------//
#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define allof(a) (a).begin(),(a).end()
using lint = long long;
template< typename T > using Vec = vector< T >;

template< typename T > bool inRange(T x, T lb, T ub) { return lb <= x && x < ub; }
template< typename T > bool inRange(T x, T y, T lb, T ub) { return in_range(x, lb, ub) && in_range(y, lb, ub); }
template< typename T > void modAdd(T& a, T b, T mod) { a = (a + b + mod) % mod; }
template< typename T > void modMul(T& a, T b, T mod) { a = (a * b) % mod; }
template< typename T > void minUpdate(T& a, T b) { a = min(a, b); }
template< typename T > void maxUpdate(T& a, T b) { a = max(a, b); }
inline int bitCount(int x) { return __builtin_popcount(x); }
inline int bitCount(lint x) { return __builtin_popcountll(x); }

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
const int Dx[8] = {0,1,1,1,0,-1,-1,-1}, Dy[8] = {-1,-1,0,1,1,1,0,-1};
const double PI = acos(-1);

//--------------8---------------->> coding space <<-----------------8-------------//

string S;
lint dp[100005][150];
const lint MOD = (lint)1e9 + 7;

int main() {
	cin >> S;
	int n = S.size();
	
	dp[0][0] = 1;
	for_(i,0,n) for_(j,0,150) {
		if (dp[i][j] == 0) continue;
		for_(k,0,10) {
			if (S[i] != '?' && k != int(S[i] - '0')) continue;
			int x = j * 10 + k;
			modAdd(dp[i+1][x % 13], dp[i][j], MOD);
		}
	}
	cout << dp[n][5] << endl;
}
//--------------8---------------->> coding space <<-----------------8-------------//

Measured memory_bytes: 117760
K, N = map(int,input().split())
lists = list(map(int,input().split()))
maxdist = 0
for i in range(N-1):
    dist = lists[i+1] - lists[i]
    if dist > maxdist:
        maxdist = dist
adis = K-lists[N-1]+lists[0]
if adis > maxdist:
    maxdist = adis

print(K-maxdist)

Measured memory_bytes: 26444
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if ( a + b >= c ){
			System.out.println("Yes");
		} 
		else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 21844
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    if (N == 1) {
        cout << "Hello World" << endl;
    } else {
        ll A, B;
        cin >> A >> B;
        cout << A + B << endl;
    }
}

Measured memory_bytes: 764
#include <iostream>
#include <complex>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
typedef complex<double> P;

#define X real()
#define Y imag()

double check(P p1, P p2, P p3, P p4)
{
    return ((p1.X-p2.X)*(p3.Y-p1.Y) + (p1.Y-p2.Y)*(p1.X-p3.X)) * ((p1.X-p2.X)*(p4.Y-p1.Y) + (p1.Y-p2.Y)*(p1.X-p4.X));
}

int main(void)
{
    double x[4],y[4];
    while(~scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",x,y,x+1,y+1,x+2,y+2,x+3,y+3)) {
        P a(x[0], y[0]);
        P b(x[1], y[1]);
        P c(x[2], y[2]);
        P d(x[3], y[3]);

        if(check(a,c,b,d) > 0.0 || check(b,d,a,c) > 0.0)
            puts("NO");
        else
            puts("YES");
    }

    return 0;
}

Measured memory_bytes: 1192
#include <stdio.h>
#define N 50


int main(int argc, const char * argv[]) {
    
    int n=0, r=0, p, c, i, j;
    int card[N],tmp[N],tmp2[N];
    
    
while (1) {
    
    
    n=0;r=0;p=0;c=0;i=0;j=0;
    
    for (i = 0; i < N; i++) {
        card[i] = 0;
        tmp[i] = 0;
        tmp2[i] = 0;
    }
    
    
    scanf("%d %d",&n,&r);
    
    
    if (n == 0 && r == 0) {
        break;
    }
    
    //cardnum
    for (i = 0; i < n; i++) {
        card[i] = n-i;
    }
    
    for (i = 0; i < r; i++) {
        
        scanf("%d %d",&p,&c);
        
        //shufflu
        //?????????????????????????????????
        for (j = 0 ; j < c; j++) {
            tmp[j] = card[p-1+j];
        }
        //tmp2
        for (j = 0; j < p-1; j++) {
            tmp2[j] = card[j];
        }
        //irerutmp1
        for (j = 0; j < c; j++) {
            card[j] = tmp[j];
        }
        
        for (j = 0; j < p-1; j++) {
            card[c + j] = tmp2[j];
        }
        
    }
    
    printf("%d\n",card[0]);
    
}
    return 0;
    
}

Measured memory_bytes: 600
D, G = map(int, input().split())
PC = [list(map(int,input().split())) for i in range(D)]

l = []
for i in range(2 ** D):
  t = 0
  c = 0
  for j in range(D):
    if ((i >> j) & 1):
      t += (j+1)*100*PC[j][0]+PC[j][1]
      c += PC[j][0]
  if t >= G:
    l.append(c)
  else:
    ck = []
    for j in range(D):
      if ((i >> j) & 1):
        continue
      else:
        ck.append(j)
    if ck == []:
      continue
    ckm = max(ck)
    for k in range(PC[ckm][0]):
      t += (ckm+1)*100
      c += 1
      if t >= G:
        l.append(c)
        break
      
print(min(l))


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

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define endl '\n'
#define debug cout << "Hold right there sparky.....\n";
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define line cout << __LINE__;
#define prv(a) for(auto x : a) cout << x << ' ';cout << '\n';
#define decimal_digits cout << fixed << setprecision(15);
#define sp cout << " ";
#define dbg2(a,b) cerr << #a << " = " << a << " " << #b << " = " << b << '\n';              

typedef unordered_map<int,int> umi;
typedef unordered_map<ll,ll> uml;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

typedef struct {
	string s;
	int t;
	int id;
}data;

bool cmp(data x,data y){

	if(x.s != y.s)return x.s < y.s;
	return x.t > y.t;
}

int main(){

	ll n;
	cin >> n;
	data d[n];

	for(ll i = 0;i < n;i++){
		cin >> d[i].s >> d[i].t;
		d[i].id = i + 1;
	}

	sort(d,d + n,cmp);

	for(ll i =0;i  < n;i++){
		cout << d[i].id << '\n';
	}

}


Measured memory_bytes: 256
/***********************************************************
	When you are inspired by passion 
	and you want to live for the current moment

	When your every thought and action
	has the power to become the story of your future

	When difficulties stand to demolish your Glory
	Just remember that Life is a 'Golden adverse Story'

	Withstand it to acheive your passion and dreams
	more amazingly more easily.

	Why then? When writing the story of your Life
	You want to Let someone else hold your pen

					huzaifa242©

***********************************************************/
#include <bits/stdc++.h>
using namespace std;
#define int int32_t
#define MAX 100005
#define x first 
#define y second

int seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l=0,int r=INT_MAX)
{return uniform_int_distribution<int>(l,r)(rng);}

template <typename T,typename G>
ostream& operator << (ostream& out, const pair<T,G> &a) 
{return out<<"( "<<a.x<<", "<<a.y<<")";}

template <typename T>
ostream& operator << (ostream& out, const vector<T> &a) 
{out<<"[ ";for(const auto &i:a)out<<i<<", ";return out<<"]"<<endl;}

template <typename T>
ostream& operator << (ostream& out, const set<T> &a) 
{out<<"{ ";for(const auto &i:a)out<<i<<", ";return out<<"}"<<endl;}

template <typename T,typename G>
ostream& operator << (ostream& out, const map<T,G> &a) 
{out<<"< ";for(const auto &i:a)out<<i<<", ";return out<<">"<<endl;}

template<typename T, size_t N>
typename enable_if<!is_same<typename remove_cv<T>::type, char>::value,
ostream&>::type operator<<(ostream& out, T(&a)[N])
{out<<"[ ";for(size_t i=0;i<N;++i)out<<a[i]<<", ";out <<"]"<<endl;return out;}

void debug_out(){cerr<<endl;} 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{cerr<<(H)<<" ";debug_out(T...);}
 
#ifdef LOCAL
#define debug(...) cerr<<"#"<<#__VA_ARGS__<<":\n",debug_out(__VA_ARGS__)
#else
#define debug(...) 24
#endif

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	char c;
	cin>>c;
	cout<<(c>='A' && c<='Z'?'A':'a');
	return 0;
}


Measured memory_bytes: 3652
#include<iostream>
#define _USE_MATH_DEFINES
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vec;
typedef vector<vector<ll>> mat;
typedef pair<ll,ll> P;
typedef map<ll,ll> MP;
typedef priority_queue<ll> PQ;
typedef stack<ll> ST;
typedef queue<ll> QUE;
#define pb push_back
#define st first
#define nd second
#define SZ(x) ((int)(x).size())
#define FOR(i,s,n) for(int i=(int)(s); i< (int)(n); i++)
#define rep(i,n) FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define each(x,c) for(auto x: (c))
#define LB(x,a) lower_bound(all(x), a)
#define UB(x,a) upper_bound(all(x), a)
const ll mod=1e9+7;
const ll INF=1e18;
const double EPS=1.0e-10;
const double PI=M_PI;

int main(){
    int N,X,Y; cin>>N>>X>>Y;
    vec num(N,0);
    FOR(i,1,N){
        FOR(j,i+1,N+1){
            int res=j-i, res1=1+abs(X-i)+abs(Y-j), res2=1+abs(X-j)+abs(Y-i);
            res=min(res, min(res1,res2));
            num[res]++;
        }
    }
    FOR(k,1,N){
        cout<<num[k]<<endl;
    }
    return 0;
}

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

using namespace std;

main(){
  int T, dp[100][100], n, d[100], s;
  cin >> T;
  while(T--){
    cin >> n;
    for(int i=0;i<n;i++) cin >> d[i];
    fill(dp[0], dp[n], 0);
    for(int k=1;k<n;k++){
      for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
          s = (i+k)%n;
          dp[i][s] = max(dp[i][s], dp[i][(i+j)%n] + dp[(i+j+1)%n][s] + abs(d[i] - d[(i+j+1)%n]));
        }
      }
    }
    int ans = 0;
    for(int i=0;i<n;i++) ans = max(ans, dp[i][(i+n-1)%n]);
    cout << ans << endl;
  }
}

Measured memory_bytes: 1196
n = int(input())
A = list(map(int,input().split()))
MOD = 10 ** 9 + 7
ret = 0
S = [A[0]]
for i in range(1, n):
  S.append(S[i-1] +A[i])

for i in range(n):
  ret += A[i] * (S[-1]-S[i])
  ret = ret % MOD
print(ret)

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

using namespace std;

int main()
{
    int n,t1,t,x1,x,y1,y;
    scanf("%d",&n);
    t1=0,x1=y1=0;
    bool ans=true;
    while(n--)
    {
        scanf("%d %d %d",&t,&x,&y);
        if(abs(x-x1)+abs(y-y1)>t-t1) ans=false;
        else if((t-t1-abs(x-x1)-abs(y-y1))%2==1) ans=false;
        t1=t;x1=x,y1=y;
    }
    if(ans) printf("Yes\n");
    else printf("No\n");
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
int main()
{
    //freopen("B.01.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    string ts;
    cin >> n;
    set<string> S;
    int old_size = 0;
    string old_string = "";
    rep(i, 0, n)
    {
        cin >> ts;
        S.insert(ts);
        if (old_size == sz(S))
        {
            cout << "No" << endl;
            return 0;
        }
        old_size++;
        if (sz(old_string) > 0)
        {
            if (ts[0] != old_string[sz(old_string) - 1])
            {
                cout << "No" << endl;
                return 0;
            }
        }
        old_string = ts;
    }
    cout << "Yes" << endl;
    // printf("%s", "Yes");
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define int64 long long
#define uint64 unsigned long long
using namespace std;

#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl

int main()
{
	int64 nn, rr = 0, gg = 0, bb = 0, ans, kk;
	string ss;
	cin >> nn >> ss;
	for(int64 ii = 0;ii < nn;ii++)
	{
		if(ss[ii] == 'R')
		{
			rr++;
		}
		else if(ss[ii] == 'G')
		{
			gg++;
		}
		else
		{
			bb++;
		}
	}
	ans = rr * gg * bb;
	for(int64 ii = 0;ii < nn;ii++)
	{
		for(int64 jj = ii + 1;jj < nn;jj++)
		{
			kk = 2 * jj - ii;
			if(kk >= nn)
			{
				break;
			}
			if(ss[ii] != ss[jj] && ss[jj] != ss[kk] && ss[kk] != ss[ii])
			{
				ans--;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3604
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (size_t i = 0; i < size_t(n); i++)
#define forn1(i,n) for (size_t i = 1; i <= size_t(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

const int MAX_N = 100010;

bool p[MAX_N + 1];
int sieve(int x) {
    fill_n(p, MAX_N + 1, true);

    p[0] = p[1] = false;
    for (ll i = 2; i <= MAX_N; i++) {
        if (p[i]) {
            if (i >= x) return i;
            for (ll j = i * i; j <= MAX_N; j += i) {
                p[j] = false;
            }
        }
    }

    assert(false);
}

int main() {
    fastio();

    int x;
    cin >> x;

    cout << sieve(x) << endl;

    return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
  while(1){
    int r,c;
    cin >> r >> c;
    if(!r && !c) break;
    if(r%2 && c%2){
      cout << "no" << endl;
    }else{
      cout << "yes" << endl;
    }
  }
}

Measured memory_bytes: 1148