akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <queue>
#include <numeric>
#include <vector>
#include <map>
#define int long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; ++i)


struct Edge {
    int src, dst, weight;
    Edge(int s, int d, int w)
        : src(s), dst(d), weight(w) { }
};
    
using Graph = vector<vector<Edge>>;

int dijkstra(const Graph &g, int s, int t) {
    const int INF = 1e18;
    using state = tuple<int, int>;
    priority_queue<state> q;
    vector<int> dist(g.size(), INF);
    dist[s] = 0;
    q.emplace(0, s);
    while (q.size()) {
        int d;
        int v;
        tie(d, v) = q.top();
        q.pop();
        d *= -1;
        if(v == t) return d;
        if (dist[v] < d) continue;
        for (auto &e : g[v]) {
            if (dist[e.dst] > dist[v] + e.weight) {
                dist[e.dst] = dist[v] + e.weight;
                q.emplace(-dist[e.dst], e.dst);
            }
        }
    }
    abort();
}

void add_edge(Graph &g, int s, int t, int w) {
    g[s].emplace_back(s, t, w);
    g[t].emplace_back(t, s, w);
}

signed main() {
    int n, m;
    while (cin >> n >> m) {
        int s, t;
        cin >> s >> t;
        --s; --t;
        Graph g(n);
        rep(i, m) {
            int a, b, c, w;
            cin >> a >> b >> c >> w;
            --a; --b; --c;
            add_edge(g, a, b, w);
            add_edge(g, b, c, w);
            add_edge(g, c, a, w);
        }
        cout << dijkstra(g, s, t) << endl;
    }
}



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

using namespace std;

long long get_nC2(long long n) {
		long long res = n * (n - 1) / 2;
		return res;
}

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

	int A[200005];
	int times[200005] = {0};
	for(int i = 0; i < N; i++){
			cin >> A[i];
			times[A[i]] += 1;
	}

	long long all = 0;
	for (int t: times) {
			all += get_nC2(t);
	}

	for (int i = 0; i < N; i++) {
			long long minus = get_nC2(times[A[i]]);
			long long plus = get_nC2(times[A[i]] - 1);
			cout << all - minus + plus << endl;
	}


}


Measured memory_bytes: 4096
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iomanip>
#include <map>

using namespace std;

#define fori(x) for (int i = 0; i < x; ++i)
#define forj(x) for (int j = 0; j < x; ++j)

int main() {
	long long a,b,c,k;
    cin>>a>>b>>c>>k;
    if(a>=k){
        cout<<k;
        return 0;
    }
    if(a+b>=k){
        cout<<a;
        return 0;
    }
    k-=a+b;
    cout<<a-k;
}

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

int main(void){
    int N, C;
    cin >> N >> C;
    int array[C][(int)1e5] = {0};
    for(int i=0; i<N; i++){
        int s, t, c;
        cin >> s >> t >> c;
        for(int j=s; j<=t; j++){
            array[c-1][j-1] = 1;
        }
    }
    int ans = 0;
    for(int i=0; i<(int)1e5; i++){
        int cnt = 0;
        for(int j=0; j<C; j++){
            cnt += array[j][i];
        }
        ans = max(ans, cnt);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 11904
#include<bits/stdc++.h>
using namespace std;
int n,k;
int h[100005];
long long dp[100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>h[i];
    }
    for(int i=0;i<n;i++)
    {
        dp[i]=999999999999999;
    }
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<i+k+1;j++)
        {
            dp[j]=min(dp[i]+abs(h[j]-h[i]),dp[j]);
        }
    }
    cout<<dp[n-1]<<endl;
    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;

namespace output{
    void __(short x){cout<<x;}
    void __(unsigned x){cout<<x;}
    void __(int x){cout<<x;}
    void __(long long x){cout<<x;}
    void __(unsigned long long x){cout<<x;}
    void __(double x){cout<<x;}
    void __(long double x){cout<<x;}
    void __(char x){cout<<x;}
    void __(const char*x){cout<<x;}
    void __(const string&x){cout<<x;}
    void __(bool x){cout<<(x?"true":"false");}
    template<class S,class T>
    void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
    template<class T>
    void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class S,class T>
    void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    void pr(){cout<<"\n";}
    template<class S,class... T>
    void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}

using namespace output;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;

#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)

const int MN = 5005;
int N, M, K, i, j, k, dp[2][MN], d, ans;
inline void add(int &x,int y){x+=y;if(x>=M)x-=M;}

int main(){
    scanf("%d%d",&N,&M);
    K = (N-1)/2;
    dp[0][0] = 1;
    for(i=1;i<=N-1;i++){
        d = min(N-i,K)-max(0,K-i+1);
        memset(dp[i&1],0,sizeof(dp[i&1]));
        for(j=0;j<N;j++){
            if(!dp[(i+1)&1][j]) continue;
            for(k=0;k*(d+1)+j<N;k++)
                add(dp[i&1][j+k*(d+1)],dp[(i+1)&1][j]);
        }
    }
    for(j=0;j<=N;j++)
        ans=(ans+1LL*(N-j)*dp[(N-1)&1][j])%M;
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    a = [1,3,5,7,8,10,12]
    b = [4,6,9,11]
    c = [2]

    some_dic = {}

    for i in a:
        some_dic[i] = 1
    for i in b:
        some_dic[i] = 2
    for i in c:
        some_dic[i] = 3

    x , y = f()

    if some_dic[x] == some_dic[y]:
        print('Yes')
    else:
        print('No')

solve()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <math.h>
#include <float.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
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; }
// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

const int MOD = 1000000007;


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

    ll seven = 0;
    ll ans = -1;
    ll count = 0;
    for(ll i = 0; i < 100000000; i++){
        seven = (seven*10 + 7) % K;
        if (seven == 0){
            ans = count+1;
            break;
        }
        count++;
    } 
    cout << ans << endl;
}

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

int main()
{
	int a,b,k;
	scanf("%d %d %d",&a,&b,&k);
	for(int i=min(a,b);i>=1;i--)
	{
		if(a%i==0&&b%i==0)
		{
			k--;
			if(!k)
			{
				printf("%d",i);
				return 0;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
#define fore(i,a) for(auto &i:a)
#define all(a) (a).begin(),(a).end()
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
using ll = long long; constexpr int inf = INT_MAX / 2; constexpr ll infl = 1LL << 60;
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; }

class Solution {
 public:
  ll solve(int N, vector<int>& A);
};

ll Solution::solve(int N, vector<int>& A) {
  map<ll,int> m;
  ll sum = 0;
  ++m[sum];

  rep(i, 0, N) {
    sum += A[i];
    ++m[sum];
  }

  ll ans = 0;
  fore(x, m) {
    ans += 1ll * x.second * (x.second-1) / 2;
  }

  return ans;
}

void _main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, 0, N) cin >> A[i];

  Solution solution;
  ll ans = solution.solve(N, A);
  cout << ans << endl;

  // vector<pair<int,vector<int>>> A = {
  //   {6, {1,3,-4,2,2,-2}},
  //   {7, {1,-1,1,-1,1,-1,1}},
  //   {5, {1,-2,3,-4,5}},
  // };

  // Solution solution;
  // fore(x, A) {
  //   int t = solution.solve(x.first, x.second);
  //   cout << t << endl;
  // }
}

Measured memory_bytes: 13568
import math 
n = int(input())

xy = [list(map(int, input().split())) for _ in range(n)]

dis = []
for i in range(n - 1):
    for j in range(i + 1, n):
        dis.append(((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])** 2) ** (1 / 2))

print(2 * math.factorial(n - 1) * sum(dis) / math.factorial(n))


Measured memory_bytes: 9372
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp> 
//using boost::multiprecision::cpp_int;
using namespace std;
#define ll long long int
#define F first
#define S second
//#define endl "\n"
//#define nl cout<<endl;
#define pb push_back
#define ull unsigned long long 
#define f(i,a,b) for(ll i=a;i<b;i++)
#define Knucklehead ios_base::sync_with_stdio(false);cin.tie(NULL);
//#define mod 100000007
#define mat vector<vector<ll>>
mat cn(ll n, ll m){return vector< vector<ll> >(n, vector<ll>(m));}
bool compare(char &s1,char &s2){return s1 > s2;} 
bool sortmahstyle(const pair<ll,ll> &a,  const pair<ll,ll> &b) 
{ 
    if(a.second > b.second )
        return true;
    if( a.second==b.second && a.first > b.second )
       return true;
    return false;
}
bool cmp(int n, pair<int, int> const& p)
{
    return (p.first < n);
}
//me
ll const mod = 1e9+7;//998244353;
ll const inf = 1e18;
ll const maxn = 1e5+1;


void solve()
{    
     
     ll a, b, c, d;
     cin >> a >> b >> c >> d;

     cout << max({ a*c, b*d , a*d, b*c});

}

int main() {
Knucklehead 
//*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
/**/ 
        
          ll t;
          /**/t=1;
          /*/cin>>t;/**/
          f(testcases,0,t){
               //cout << "Case #" <<testcases+1<<": ";
               solve();
          }
 
 
    return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cmath>
#include <utility>

using namespace std;

using ll = long long;
using p = pair<ll, ll>;

int main(void) {
  ll N;
  cin >> N;
  vector<vector<ll> > mat(N, vector<ll>(N, 1));
  ll parity = N % 2;
  ll M = N - parity;
  for (ll i = 0; i < M; i++) {
    ll j = M - 1 - i;
    mat[i][i] = 0;
    mat[i][j] = 0;
    mat[j][i] = 0;
    mat[j][j] = 0;
  }
  if (parity) {
    mat[N - 1][N - 1] = 0;
  }

  ll count = 0;
  vector<p> edges;

  for (ll j = 0; j < N; j++) {
    for (ll i = 0; i < j; i++) {
      if (mat[i][j]) {
        count++;
        edges.push_back(p(i + 1, j + 1));
      }
    }
  }

  cout << count << endl;
  for (auto e : edges) {
    cout << e.first << " " << e.second << endl;
  }
  
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
using namespace std;
int main()
{
    int N, K;
    cin >> N >> K;
    int d(1);
    while (N >= K) {
        d++;
        N /= K;
    }
    cout << d << endl;
    return 0;
}

Measured memory_bytes: 256
S = input()
S = list(S)

if S[0]==S[1] and S[2]==S[3] and S[0]!=S[2]:
    print('Yes')

elif S[0]==S[2] and S[1]==S[3] and S[0]!=S[1]:
    print('Yes')

elif S[0]==S[3] and S[1]==S[2] and S[0]!=S[1]:
    print('Yes')

else:
    print('No')


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
 
using namespace std;
#define mod 1000000007
#define ll long long 
 
 
ll n,w, a[100009], b[100009];
ll dp[109][100009];
 
// map<int, map<ll, ll> > dp;
 
ll solve(int r, int idx) {
    if(idx == n)
        return r == 0 ? 0 : INT_MAX;
 
    if(dp[idx][r] != -1)
    	return dp[idx][r];
 
    ll ans = solve(r, idx + 1);
    if(b[idx] <= r)
    	ans = min(ans, a[idx] + solve(r - b[idx], idx + 1));
 
    return dp[idx][r] = ans;
}
 
int s(int v_max) {
 
	for(int i = v_max; i >= 0; i--) {
		if(solve(i, 0) <= w)
			return i;
	}
	return 0;
}
 
int main() {
 
    // int t;
    // cin>>t;
    // while(t--) {
        cin>>n>>w;
        memset(dp, -1, sizeof(dp));
 
        int v_max = 0;
 
        for(int i = 0; i < n; i++) {
            cin>>a[i]>>b[i];
            v_max += b[i];
        }
 
        cout<<s(v_max)<<endl;
 
}
 

Measured memory_bytes: 88804
#include <iostream>
#include<algorithm>
#include<math.h>
#include<cstring> 
#include <queue>
#include <vector>
#include <map>
#define MAXN 2e5+7

using namespace std;

int main()
{
	int a,p;
	cin>>a>>p;
	int sum=a*3+p;
	if(a==0 && p<2)
	cout<<0<<endl;
	else
	cout<<sum/2<<endl;
	return 0;
 } 

Measured memory_bytes: 764
dish = [int(input()) for _ in range(5)]
dish_10 = []
dish_1 = []
for i in dish:
    if(i%10==0):
        dish_10.append(int(i/10))
        dish_1.append(10)
    else:
        dish_10.append(int(i/10)+1)
        dish_1.append(i%10)
last = dish_1.index(min(dish_1))
ans = 0
for index,i in enumerate(dish_10):
    if(index!=last):
        ans+=i*10
ans += dish[last]
print(ans)


Measured memory_bytes: 3064
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] s = sc.next().toCharArray();
        int ans = 0;
        char prev = '0';
        for(char c : s){
            if(prev != c){
                ans++;
            }
            prev = c;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 26504
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#define ll long long
#define rep(i, a, b) for (int i = a; i <= (int)b; i ++)
void read(int & x) {
    x = 0; int flag = 1; char ch = ' ';
    while (ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= flag;
}
void read(ll & x) {
    x = 0; int flag = 1; char ch = ' ';
    while (ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= flag;
}
using namespace std;
const int maxn = 2010;
int n, degree[maxn], a[maxn];
bool vis[maxn], mp[maxn][maxn];
vector < int > ans, edge[maxn];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
void dfs(int u) {
    vis[u] = 1;
    rep(i, 1, n)
        if(!vis[i] && mp[u][i]) edge[u].push_back(i), degree[i] ++, dfs(i);
}
void solve() {
    priority_queue < int > pq;
    memset(vis, 0, sizeof(vis));
    rep(i, 1, n) if(degree[i] == 0) pq.push(i), vis[i] = 1;
    while(!pq.empty()) {
        int u = pq.top(); pq.pop();
        ans.push_back(u);
        rep(i, 0, edge[u].size() - 1) {
            int v = edge[u][i];
            if(-- degree[v] == 0) pq.push(v);
        }
    }
}
int main()
{
    read(n);
    rep(i, 1, n) read(a[i]);
    sort(a + 1, a + 1 + n);
    rep(i, 1, n - 1) rep(j, i + 1, n) 
        if(gcd(a[i], a[j]) != 1) mp[i][j] = mp[j][i] = 1;
    rep(i, 1, n) dfs(i);
    solve();
    rep(i, 0, n - 1) printf("%d ", a[ans[i]]);
    return 0;
}

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

klist = []
sdict = {}
for m in range(M):
    tmp = list(map(int, input().split()))
    klist.append(tmp[0])
    sdict[m] = tmp[1:]
plist = list(map(int, input().split()))

def solve(N, plist, switch_num):
    global M
    num = 0

    if N == 1:
        idx = []
        idx2 = []
        count = 0
        for m in range(M):
            if switch_num in sdict[m]:
                count += 1
                idx.append(plist[m])
            else:
                idx2.append(plist[m])
        if sum(idx) == len(idx) or sum(idx) == 0:
            if sum(idx2) == 0:
                if count == 0:
                    return 2
                else:
                    return 1
            else:
                return 0
        else:
            return 0

    # switch1 == OFF
    new_plist = plist
    num += solve(N-1, new_plist, switch_num+1)
    
    # switch1 == ON
    new_plist = []
    for i in range(M):
        if switch_num in sdict[i]:
            new_plist.append(1 - plist[i])
        else:
            new_plist.append(plist[i])
    num += solve(N-1, new_plist, switch_num+1)

    return num

print(solve(N, plist, 1))


Measured memory_bytes: 44140
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  int counter;
  cin >> n;
  vector<int> a(n);
  counter = 0;
 
 for(int i =0; i < n; i++){
   cin >> a.at(i);
   }

 for(int j = 0; j < 10000; j++){
    for(int i =0; i < n; i++){
        if(a.at(i) % 2 == 0){
            a.at(i) = a.at(i) / 2;
            if(i == n - 1){
                counter = counter + 1;
            }
        }else{
            break;
        }
    }
   }
    cout << counter << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;
using P = pair<int, int>;

const int INF = 1001001001;
const vector<int> di = {-1,  0, 1, 0};
const vector<int> dj = { 0, -1, 0, 1};

void chmin(int &a, int b) { if (a > b) a = b; }

ll GCD(ll a, ll b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
ll LCM(ll a, ll b) { return a * b / GCD(a, b); }


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

    ll ans = 0;
 
    if (x % 11 > 6) {
        ans = (x / 11) * 2 + 2;
    } else if (x % 11 > 0) {
        ans = (x / 11) * 2 + 1;
    } else {
        ans = (x / 11) * 2;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
a,b,k = map(int, input().split())
s = []
for i in range(a,min(a+k,b+1)):
  s.append(i)
for i in range(max(a,b-k+1,a+k),b+1):
  s.append(i)
sorted(s)
for i in s:
  print(i)

Measured memory_bytes: 9092
#include <bits/stdc++.h>
#define ms(x, a) memset(x, a, sizeof(x))
#define oo 100000000
#define ll long long int
#define MOD 1000000007
using namespace std;
int main()
{
    ll h,a;
    cin>>a>>h;
    ll  sum =0;
    vector<ll>v;
    while(a--){
        ll b;
         cin>>b;
        v.push_back(b);
    }
    sort(v.rbegin(),v.rend());
    ll  ans =0 ;
    for(int i=h;i<v.size();i++)ans+=v[i];
    cout<<ans;

    return 0;
}



Measured memory_bytes: 2420
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=list(map(int,input().split()))
    if n==0:
        if A[0]==1:
            print(1)
        else:
            print(-1)
        exit()
    C=[0]*(n+1)
    flag=True
    ans=1
    if A[0]==1:
        C[0]=0
        c=0
    else:
        C[0]=1
        c=1
    for i in range(n):
        a=A[i+1]
        c*=2
        ans+=c
        C[i+1]=c
        if c<a:
            flag=False
            break
        else:
            c-=a
    if flag:
        for i in range(n):
            if c>0:
                ans-=c
                c-=C[n-i]//2
            else:
                break
        print(ans)
    else:
        print(-1)
if __name__ == '__main__':
    main()

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

int mod = 'z' - 'a' + 1;

int main() {
	string s;
	cin >> s;
	int n = s.size();

	int m;
	cin >> m;
	vector<vector<int>> graph(n/2 + 1);
	for(int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a;
		a = min(a, n-a);
		b = min(b, n-b);
		if(a != b) {
			graph[a].push_back(b);
			graph[b].push_back(a);
		}
	}

	vector<int> vec(n/2);
	for(int i = 0; i < n/2; ++i) {
		vec[i] = int(s[i]) - int(s[n-1-i]);
		vec[i] %= mod;
		vec[i] += mod;
		vec[i] %= mod;
	}

	n  = n/2+1;

	vector<bool> seen(n, false);
	function<void(int, vector<int>&)> dfs = [&](int node, vector<int> &comp) {
		if(seen[node]) return;
		seen[node] = true;
		comp.push_back(node);
		for(int ch : graph[node]) dfs(ch, comp);
	};

	vector<int> finish(n, -1);
	vector<int> start(n, -1);
	vector<int> total;
	for(int i = 0; i < n; ++i) {
		if(!seen[i]) {
			vector<int> comp;
			dfs(i, comp);
			sort(comp.begin(), comp.end());
			for(int j = 1; j < comp.size(); ++j) {
				start[comp[j-1]] = total.size();
				finish[comp[j]] = total.size();
				total.push_back(0);
			}
		}
	}

	int sum = 0;
	bool can = true;
	for(int i = 0; i < n-1; ++i) {
		assert(vec[i] >= 0);
		assert(sum >= 0);
		vec[i] += sum;
		vec[i] %= mod;
		if(vec[i] != 0) {
			if(start[i] == -1) can = false;
			else {
				sum += mod - vec[i];
				sum %= mod;
				total[start[i]] = (mod - vec[i]) % mod;
			}
		}
		if(finish[i+1] != -1) {
			sum += mod - total[finish[i+1]];
			sum %= mod;
		}
	}

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

Measured memory_bytes: 6652
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <queue>
#include <stack>
#include <deque>
#define ll long long
#define endl '\n'
using namespace std;

int main(void)
{
  cin.tie(NULL); ios_base::sync_with_stdio(false);
  int N; cin >> N;
  ll ret = 0;
  while(N--)
    {
      int l, r; cin >> l >> r;
      ret += (r - l) + 1;
    }

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



Measured memory_bytes: 888
package main

import(
    "fmt"
    "sort"
    "strings"
)



func main() {
    var a,b int
    fmt.Scan(&a,&b)
    ans := max32(a,b)*2
    if a!=b{
        ans--
    }
    fmt.Println(ans)
}





func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

func min32(a, b int) int {
    if a >= b {
        return b
    }
    return a
}

func max32(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}

func scanNums(len int) (nums []int){
    var num int
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanNums64(len int) (nums []int64){
    var num int64
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanString(len int) (str []string){
    var s string
    for i:=0; i<len; i++{
        fmt.Scan(&s)
        str = append(str,s)
    }
    return
}

func scanTwoNums(n,m int) ([][]int){
    Nums := make([][]int, n)
    for i:=0; i<n; i++{
        Nums[i] = make([]int, m)
    }
    return Nums
}

func SortString(s string) string{
    t := strings.Split(s, "")
    sort.Strings(t)
    return strings.Join(t, "")
}


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

int main() {
  string s; cin >> s;
  int y = stoi(s.substr(0,4));
  int m = stoi(s.substr(5,2));
  int d = stoi(s.substr(8,2));
  int ok = true;
  if (y < 2019) {ok = false;}
  if (y == 2019 && m < 4) {ok = false;}
  if (y == 2019 && m == 4 && d <= 30) {ok = false;}
  if (ok) {cout << "TBD" << endl;}
  else {cout << "Heisei" << endl;}
}


Measured memory_bytes: 256
import java.util.*;

class Main {
	Scanner sc;
	
	private void calc() {
		sc = new Scanner(System.in);
		int H = sc.nextInt();
		int A = sc.nextInt();
		System.out.println((H+A-1)/A);
	}

	public static void main(String[] args) {
		new Main().calc();
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
#define ALL(x) (x).begin(), (x).end()
LL POW(LL a,LL p,LL M){ if(!p) return 1LL;LL T = POW(a,p/2,M);T = T*T%M; if(p&1) T=T*(a%M)%M; return T; }
LL SQRT(LL a) { LL b = (LL)sqrtl(((double)a)+0.5); while(b*b<a) ++b; while(b*b>a) --b; return (b*b==a)?b:-1; }
//endl
//<------------------------edits---------------------------------------------->
const LL MOD = 1e9+7;//998244353
// #define LOCAL LDD
// #define int LL
int fq[2002];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);cout << fixed;
#ifdef LOCAL
  freopen("input.txt", "rt", stdin);
#endif
  
  int n;cin >> n;
  vector<int> v(n);
  for(int i=0;i<n;i++) cin >> v[i],fq[v[i]]++;
  for(int i=1;i<2002;i++) fq[i] += fq[i-1];
  LL f = 0;
  sort(ALL(v));
  for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){
    int l = v[j]-v[i];
    int r = v[j]+v[i];
    f += fq[r-1] - fq[l];
    if(v[i]>l&&v[i]<r) f--;
    if(v[j]>l&&v[j]<r) f--;
  }
  f /= 3;
  cout << f << endl;

  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";
  return 0;
}

Measured memory_bytes: 256
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <math.h>
#include <set>
#include <vector>
#include <algorithm>
#include <map>


using namespace std;

typedef long long ll;
const double PI = acos(-1.0);
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define AN 100005

int N, K;
ll a[AN];

int main(){
    int i, j;
    ll t, *p, ans;
    while(scanf("%d%d", &N, &K)!=EOF){
        ans = 0x7fffffffffffffff;
        for(i = 1; i <= N; i++){
            scanf("%lld", &t);
            if(t == 0){
                K--, N--, i--;
                continue;
            }
            a[i] = t;
        }
        if(!N){
            printf("0\n");
            continue;
        }
        p = lower_bound(a+1, a+1+N, 0);
        i = MAX((p-a)-K, 1);
        j = i+K-1;
        while(i<=p-a && j<=N){
            if(a[i]*a[j] < 0)
                ans = MIN(MIN(abs(a[i])*2+a[j], abs(a[i])+a[j]*2), ans);
            else
                ans = MIN(ans, MAX(abs(a[i]), abs(a[j])));
            i++, j++;
        }
        printf("%lld\n", ans);
    }

    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	
	private static final int VACANT = 0;
	private static final int BLOCK = 1;
	private static final int START = 2;
	private static final int GOAL = 3;
	private static final int HOLE = 4;
	private static final int VX[] = new int[]{ 1, 0, -1, 0 };
	private static final int VY[] = new int[]{ 0, 1,  0, -1 };
	private Scanner sc; 

	private int[][] board;
	private void run() {
		sc = new Scanner( System.in );
		while( true ) {
			int h, w;
			int curY = 0, curX = 0;
			w = sc.nextInt();
			h = sc.nextInt();
			if( w == 0 && h == 0 ){ break; }
			board = new int[ h + 2 ][ w + 2 ];
			for( int x = 0; x < w + 2; x++ ) {
				board[ 0 ][ x ] = HOLE;
				board[ h + 1 ][ x ] = HOLE;
			}
			for( int y = 0; y < h + 2; y++ ) {
				board[ y ][ 0 ] = HOLE;
				board[ y ][ w + 1 ] = HOLE;
			}
			for( int y = 1; y < h + 1; y++ ) {
				for( int x = 1; x < w + 1; x++ ) {
					board[ y ][ x ] = sc.nextInt();
					if( board[ y ][ x ] == START ) {
						board[ y ][ x ] = VACANT;
						curX = x;
						curY = y;
					}
				}
			}
			int minpt = Integer.MAX_VALUE;
			for( int i = 0; i < VX.length; i++ ) {
				int pt = dfs( 1, curX, curY, i );
				if( pt != -1 && pt < minpt ) { minpt = pt; }
			}
			if( minpt == Integer.MAX_VALUE ) { minpt = -1; }
			System.out.println( minpt );
		}
	}
	public int dfs( int depth, int x, int y, int dir ) {
		if( depth > 10) { return -1; }

		int dest = board[ y + VY[ dir ] ][ x + VX[ dir ] ];
		if( dest == BLOCK || dest == HOLE ) {
			return -1;
		}
		/*
				System.err.println( moves + " " + dir );
				for( int ly = 0; ly < b.length; ly++ ){
					for( int lx = 0; lx < b[ ly ].length; lx++ ){
						if( ly == y && lx == x ) { System.err.print( "P"); }
						else {System.err.print( b[ ly ][ lx ] );}
					}
					System.err.println();
				}
				System.err.println();
		 */
		while( board[ y ] [ x ] == VACANT ) {
			x += VX[ dir ];
			y += VY[ dir ];
		}

		if(board[ y ][ x ] == BLOCK ) {
			board[ y ][ x ] = VACANT;
			int minpt = Integer.MAX_VALUE;
			for( int i = 0; i < VX.length; i++ ) {
				int pt = dfs( depth + 1, x - VX[ dir ], y - VY[ dir ], i );
				if( pt != -1 && pt < minpt ) { minpt = pt; }
			}
			if( minpt == Integer.MAX_VALUE ) { minpt = -1; }
			board[ y ][ x ] = BLOCK;
			return minpt;
		} else if( board[ y ][ x ] == GOAL ) {
			return depth;
		} else {
			return -1;
		}
	}
	
	public static void main( String[] args ) {
		new Main().run();
	}
}

Measured memory_bytes: 37720
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    if(a % 2 != 0 && b % 2 != 0){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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



int main(){
    int64_t n ;
    int64_t k ;
    cin >> n >> k ;
    vector<int> a(n) ;
    for (size_t i = 0; i < n; i++)
    {
        cin >> a.at(i) ;
    }
    vector<int> perm(1) ;
    vector<bool> moumita(n,0) ;
    moumita.at(0) = 1 ;
    perm.at(0) = 1 ;
    int64_t i = 0 ;
    while (1)
    {
        if (moumita.at(a.at(perm.at(i)-1)-1) == 0 )
        {
            perm.push_back(a.at(perm.at(i)-1)) ;
            moumita.at(a.at(perm.at(i)-1)-1) = 1 ;
            i ++ ;

        }else
        {
            perm.push_back(a.at(perm.at(i)-1)) ;
            i ++ ;
            break ;
        }
        
        
    }
    int64_t ans = 0 ;
    for (size_t i = 0; i < perm.size(); i++)
    {
        if (perm.at(i) == perm.at(perm.size()-1))
        {
            if (k <= i)
            {
                ans = k ;
            }else
            {
                ans = (k-i) % (perm.size()-1 -i) + i ;
            }
            
            break ;
        }
        
    }
    
    cout << perm.at(ans) << endl ;
}

Measured memory_bytes: 5128
#include <iostream>

void swap(int& a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

int main()
{
	int N;
	std::cin >> N;
	
	int *A = new int[N];
	for (int i=0; i<N; i++) std::cin >> A[i];
	
	int swap_count = 0;
	for (int i=0; i<N; i++) {
		for (int j=N-1; j>i; j--) {
			if (A[j-1] > A[j]) {
				swap(A[j-1], A[j]); swap_count++;
			}
		}
	}
	
	std::cout << A[0];
	for (int i=1; i<N; i++) std::cout << " " << A[i];
	std::cout << std::endl;
	std::cout << swap_count << std::endl;
	
	delete[] A;
	
	return 0;
}




Measured memory_bytes: 3092
package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
	"strings"
)

func main() {
	n, arr := readArr()

	swap := true // 逆順の隣接要素が存在する
	i := 0       // 未ソート部分の先頭index
	swappedCnt := 0

	for swap {
		swap = false
		for j := n - 1; j > i; j-- {
			if arr[j] < arr[j-1] {
				tmp := arr[j]
				arr[j] = arr[j-1]
				arr[j-1] = tmp
				swap = true
				swappedCnt++
			}
		}
		i++
	}

	printArr(arr)
	fmt.Println(swappedCnt)
}

func checkErr(e error) {
	if e != nil {
		log.Fatalln(e)
	}
}

func readArr() (int, []int) {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, err := strconv.Atoi(scanner.Text())
	checkErr(err)

	arr := make([]int, n)
	scanner.Scan()
	for i, s := range strings.Split(scanner.Text(), " ") {
		arr[i], err = strconv.Atoi(s)
		checkErr(err)
	}
	return n, arr
}

func printArr(arr []int) {
	s := strings.Trim(fmt.Sprint(arr), "[]")
	fmt.Println(s)
}



Measured memory_bytes: 1164
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

fn main() {

    let n: u32 = read();
    let mut a: Vec<(u32, u32)> = (0..n).map(|x| (read(),x + 1)).collect();
    a.sort_by(|x, y| x.0.cmp(&y.0));

    for i in a.iter() {
        print!("{} ", i.1);
    }
}


Measured memory_bytes: 4860
class UnionFind
  attr :parent, :rank

  def initialize
    @parent = Hash.new
    @rank = Hash.new
  end

  def make(x)
    @parent[x] = x
    @rank[x] = 0
  end

  def union(a, b)
    x, y = find(a), find(b)
#     x, y = y, x if @rank[x] < @rank[y]
    x, y = y, x unless x < y
    @parent[y] = x
    @rank[x] += 1 if @rank[x] == @rank[y]
  end

  def find(x)
    @parent[x] == x ? x : @parent[x] = find(@parent[x])
  end

  def size
    @parent.keys.map{|k| find(k)}.sort.uniq.size
  end
end

N, M, K = gets.split.map &:to_i

group = UnionFind.new
1.upto(N) do |i|
  group.make(i)
end
1.upto(M) do |i|
  group.make(-i)
end

ans = 0
1.upto(K) do |i|
  a, b, c = gets.split.map &:to_i
  case a
    when 1
      x = group.find(b)
      y = group.find(c)
      if x < 0 && y < 0 && x != y
        ans = i
        break
      end
      group.union(x, y)
    when 2
      x = group.find(b)
      y = -c
      if x < 0 && x != y
        ans = i
        break
      end
      group.union(x, y)
  end
end
p ans

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

int main() {
  int N;
  cin >> N;
  vector<long long int> A(N);
  long long int sum=0;

  for(int i=0; i<N; i++){
    cin  >> A.at(i);
    if(i==0) continue;
    if(A.at(i-1)>A.at(i)){
      sum+=(A.at(i-1)-A.at(i));
      A.at(i)=A.at(i-1);
    }
  }

  cout << sum <<endl;


}


Measured memory_bytes: 4848
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#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 <fstream>
#include <iomanip>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(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 FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,(n))
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 2;
const int MOD = 1000000007;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main() {
	vi prime(100000, 1);
	prime[0] = prime[1] = 0;
	FOR(i, 2, sqrt(100000)) {
		for (int j = i*i; j < 100000; j += i) {
			prime[j] = 0;
		}
	}

	vi ans;
	REP(i, 100000) {
		if (prime[i] && i % 5 == 1) {
			ans.push_back(i);
		}
	}

	int N;
	cin >> N;
	REP(i, N) {
		cout << ans[i] << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int Int() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Int() + add;
        }
        return Array;
    }

    public long Long() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Long() + add;
        }
        return Array;
    }
}
class Program {
    static Scanner cin = new Scanner();
    static void Main() {
        int H = cin.Int();
        int W = cin.Int();
        var S = Enumerable.Repeat(0, H).Select(_ => Console.ReadLine()).ToArray();
        var line = new bool[H];
        var row = new bool[W];
        for (int i = 0; i < H; i++) { 
            for (int j = 0; j < W; j++) {
                if(S[i][j] == '#') {
                    line[i] = true;
                    row[j] = true;
                }
            }
        }

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (line[i] && row[j]) {
                    Console.Write(S[i][j].ToString());
                }
            }
            if(line[i])Console.WriteLine();
        }
        Console.ReadLine();
    }
}

Measured memory_bytes: 13396
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*n
        

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

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

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                #ランクの更新
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1


n,m = map(int,input().split())
ufpc = UnionFindPathCompression(n)
for _ in range(m):
    a,b = map(int,input().split())
    a,b=a-1,b-1
    ufpc.union(a,b)

for i in range(n):
    ufpc.find(i)

c = collections.Counter(ufpc.parents)
score_sorted = sorted(c.items(), key=lambda x:-x[1])
print(score_sorted[0][1])


Measured memory_bytes: 116284
#include<iostream>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class question {
public:
	string s;
	int K;
	
	void ans() {
		cin >> s >> K;
		int N = s.size();
		set<string> st;
		for (int i = 0;i < N;i++) {
			for (int j = 1;j <= min(N - i, K);j++) {
				st.insert(s.substr(i, j));
			}
		}
		set<string>::iterator itr = st.begin();
		REP(i, K - 1) itr++;
		cout << *itr << "\n";
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	question q;
	q.ans();
	
	return 0;
}



Measured memory_bytes: 1664
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
//typedef __int64 LL;
//typedef long long int LL;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef pair<int,int> P;
//typedef pair<LL,LL> PL;

const int MOD=1000000007;

void ans(bool flag)
{
	if(flag)cout<<"Yes"<<"\n";
	else cout<<"No"<<"\n";
}

int main(){
	int k;cin>>k;
	string s;cin>>s;
	if(s.length()<=k)cout<<s<<"\n";
	else
	{
		cout<<s.substr(0,k)<<"..."<<"\n";		
	}
	
	return 0;
}

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

typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int,int> pii;
typedef priority_queue< int, vector< int >, greater< int > >  minHeap;

#define ones(x) __builtin_popcount(x)
#define onesl(x) __builtin_popcountl(x)
#define onesll(x) __builtin_popcountll(x)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define scn(n) scanf("%d",&n)
#define scnll(n) scanf("%lld",&n)
#define scn2(n,m) scanf("%d%d",&n,&m)
#define scn3(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scn2ll(n,m) scanf("%lld%lld",&n,&m)
#define atoz(v) v.begin(),v.end()
#define ratoz(v) v.rbegin(),v.rend()
#define Fill(a,v) memset(a,v,sizeof(a))
#define fi first
#define se second
#define inf 1e9
#define pi acos(-1.0)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define mod 1000000007
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bug(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"

int Set(int N,int pos)
{
    return N=N | (1<<pos);
}
int reset(int N,int pos)
{
    return N = N & ~(1<<pos);
}
bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}

inline int addmod(lli x,lli y)
{
    return (x%mod + y%mod)%mod;
}
inline int submod(lli x,lli y)
{
    return (x%mod - y%mod + mod)%mod;
}
inline int mulmod(lli x,lli y)
{
    return (x%mod * y%mod)%mod;
}


inline int nextSubMask(int i, int mask)
{
    return (i-1)&mask;   /// returns next  submask
}

template<typename T>
void we_r_done(T mssg)
{
    cout<<mssg;
    exit(0);
}

int main()
{
    ///freopen("output.txt","w",stdout);
   //freopen("input.txt","r",stdin);
    FastIO;

    int n;
    while(cin>>n){

        vector<pii>v;

        int lo=1, hi = n-(n%2);

        for(lo++ , hi-- ; lo<hi; lo++, hi--){

            v.pb({lo,lo-1});
            v.pb({lo,hi+1});

            v.pb({hi,lo-1});
            v.pb({hi,hi+1});
        }

        if(n%2){
            lo--;
            hi++;
            v.pb({n,lo});
            v.pb({n,hi});
        }

        if(n > 4){
            if(n%2){
                v.pb({n,n-1});
                v.pb({n,1});
            }
            else{
                lo = n/2;
                hi = lo+1;

                v.pb({1,lo});
                v.pb({n,lo});

                v.pb({1,hi});
                v.pb({n,hi});
            }
        }

        cout<<v.size()<<endl;

        for(pii p : v) cout<<p.fi<<" "<<p.se<<endl;

        //cout<<"\n\n\n";

    }

    return 0;
}

///sin and cos expect input in radians not degrees. so use , sin(degrees * pi / 180)
///using bs = bitset<MX>; // how many distinct number can be form?
///sort(atoz(v), [](const data x, const data y){return (x.a==y.a?x.b>y.b : x.a<y.a);});


Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <functional>
#include <cassert>
#include <utility>
#include <stack>
#include <queue>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef pair<int,int> Pi;
typedef long long int ll;
const int INF=(1<<30)-1;
const ll INFl=9223372036854775807;
const int MAX=10000;
const ll MOD=998244353;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n;

int main(){
	cin>>n;
	int m;
	if(n%2==0)
		m=(n-2)*n/2;
	else 
		m=(n-1)*(n-1)/2;
	cout<<m<<endl;
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			if((n%2==0&&i+j!=n+1)||(n%2==1&&i+j!=n)){
				cout<<i<<" "<<j<<endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
x,y,a,b,c = map(int, input().split(" "))
plist= sorted(list(map(int, input().split(" "))),reverse=True)[0:x]
qlist= sorted(list(map(int, input().split(" "))),reverse=True)[0:y]
rlist= sorted(list(map(int, input().split(" "))),reverse=True)

plist.extend(qlist)
plist.sort()
n = min(x+y,len(rlist))
i = 0

while i < n and rlist[i]>plist[i]:
  i += 1
if i == 0:
  print(sum(plist))
else:
  print(sum(plist[i:x+y])+sum(rlist[0:i]))


Measured memory_bytes: 22504
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int n;
	cin >> n;
	
	vector<ll> a(n);
	int even = 0;
	priority_queue<ll> q;
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		if( a[i] % 2 == 0 ) { 
			even++;
			q.push(a[i]);
		}
	}
	
	if( q.empty() ) { 
		cout << 0 << endl;
		return 0;
	}
	
	int cnt = 0;
	while( !q.empty() ) {
		ll tmp = q.top();
		q.pop();
		
		if( cnt == 0 && tmp % 2 == 0 )  {
			q.push(tmp / 2);
			cnt++;
		}
		
		else if( (3 * tmp) % 2 == 0 ) { 
			q.push( (3 * tmp) / 2 );
			cnt++;
		}
	}
	
	cout << cnt << endl;
	
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;


int main(){

  ll n, k;
  cin >> n >> k;
  vector<ll> h(n);
  REP(i,n) cin >> h[i];

  ll sum = 0;
  sort(ALL(h));

  if(n <= k){
    cout << 0 << endl;
    return 0;
  }

  // if(k == 0){
  //   for(int i = 0; i < n; i++) sum += h[n];
  // }
  else{
    for(int i = 0; i < n-k; ++i){
      sum += h[i];
    }
  }
  cout << sum << endl;

  return 0;
}

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

//#define int long long

using namespace std;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int maxn = 1e5+5;
    int a[maxn];
    int bad[maxn];
    int good[maxn];
    int cnt[maxn];
    for (int i = 0; i < maxn; i++) {
        cnt[i] = bad[i] = good[i] = a[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    for (int i = 0; i < maxn; i++) {
        if (cnt[i]%2==1) bad[i%m]++;
        good[i%m] += (cnt[i]/2)*2;
        /*if (cnt[i] >= 1) {
            cout << " now bad " << i%m << " is " << bad[i%m] << '\n';
            cout << " good " << i%m << " is " << good[i%m] << '\n';
        }*/
    }

    int res = 0;

    for (int i = 0; i < m; i++) {
        int j = (m-i)%m;
        /*cout << " i = "<< i << " j = " << j << "\n";
        cout << " good i: " << good[i] << " bad i: " << bad[i] << '\n';
        cout << " good j: " << good[j] << " bad j: " << bad[j] << '\n';
        cout << "RES BEFORE: " << res<<'\n';*/
        if (i == j) {
            res += ((good[i]+bad[i])/2);
        } else {
            int amt = min(bad[i], bad[j]);
            res += amt;
            bad[i] -= amt;
            bad[j] -= amt;
            //cout << " amt = " << amt << '\n';
            if (bad[i] < bad[j]) {
                res += max((good[i]-min(bad[j],good[i]))/2 + min(bad[j], good[i]), good[i]/2);
                res += good[j]/2;
            } else if (bad[j] < bad[i]){
                res += max((good[j]-min(bad[i],good[j]))/2 + min(bad[i], good[j]), good[j]/2);
                res += good[i]/2;
            } else {
                res += good[i]/2;
                res += good[j]/2;
            }
        }
        good[i] = good[j] = bad[i] = bad[j] = 0;
        //cout << "RES AFTER: " << res << '\n';
    }
    cout << res << '\n';
}
/*

 */

Measured memory_bytes: 5180