akhauriyash/Code-Regression huggingface dataset:
#ifdef _MSC_VER
#  define _CRT_SECURE_NO_WARNINGS
#  define _USE_MATH_DEFINES
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#include <bits/stdc++.h>
using namespace std;
using i32 = int; using i64 = long long int; using f64 = double;
using u32 = unsigned int; using u64 = unsigned long long int; using str = string;
template <typename T> using vec = vector<T>; void in() { }
template <typename T, typename...TS> void in(T &&x, TS &&...xs) { cin >> x; in(move(xs)...); }
template <typename T> void out(T &&x) { cout << x << "\n"; }
template <typename T, typename...TS> void out(T &&x, TS &&...xs) { cout << x << " "; out(move(xs)...); }
#define indef(t, ...) t __VA_ARGS__; in(__VA_ARGS__)
#define get(t) []{ t x; cin >> x; return x; }()
#define times(n, i) for (i32 i = 0; i < (n); ++i)
#define range(a, b, i) for (i32 i = (a); i < (b); ++i)
#define upto(a, b, i) for (i32 i = (a); i <= (b); ++i)
#define downto(a, b, i) for (i32 i = (a); i >= (b); --i)
#define all(xs) (xs).begin(), (xs).end()
#define sortall(xs) sort(all(xs))
#define reverseall(xs) reverse(all(xs))
#define even(x) ((abs(x) & 1) == 0)
#define odd(x) ((abs(x) & 1) == 1)
#define bit(x, i) (((x) >> i) & 1)
#define append emplace_back
#define bisect_left lower_bound
#define bisect_right upper_bound
#define bound(a, x, b) (a <= x && x <= b)
const i64 MOD = 1000000007ll;
const f64 EPS = 1e-10;

bool p[100001];
bool b[100001];
int s[100001];

int solve() {
    indef(int, l, r);
    return s[r] - s[l-1];
}

void init() {
    memset(&p, true, sizeof(p));
    for (int f = 2; f <= 50000; f++) {
        for (int i = f+f; i <= 100000; i += f) {
            p[i] = false;
        }
    }
    p[1] = false;

    memset(&b, false, sizeof(b));
    for (int i = 1; i < 100001; i += 2) {
        b[i] = p[i] && p[(i+1)/2];
    }

    int t = 0;
    for (int i = 1; i < 100001; i++) {
        t += (b[i] ? 1 : 0);
        s[i] = t;
    }
}

i32 main()
{
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(9);

#ifdef _MSC_VER
    /**
    ifstream fin("input.txt"); cin.rdbuf(fin.rdbuf()); assert(fin);
    ofstream fout("output.txt"); cout.rdbuf(fout.rdbuf()); assert(fout);
    /**/
#endif

    init();

    indef(int, q);
    times(q, i) {
        out(solve());
    }

#ifdef _MSC_VER
    /**/
    /**/
#endif
    return 0;
}

Measured memory_bytes: 1280
A = input()
B = A.split()
a = int(B[0])
b = int(B[1])
c = int(B[2])
d = int(B[3])

if a <= 0 and b <= 0 and c <= 0 and d <= 0:
    print(a*c)
elif a > 0 and b > 0 and c > 0 and d > 0:
    print(b*d)
elif a > 0 and b > 0 and c<=0 and d<=0:
    print(a*d)
elif a<=0 and b<=0 and c>0 and d>0:
    print(b*c)
elif a<=0 and b<=0 and c<=0 and d>0:
    print(a*c)
elif a>0 and b>0 and c<=0 and d>0:
    print(b*d)
elif a <= 0 and b > 0:
    if c <= 0 and d > 0:
        if -c <= d and -a <= b:
            print(d*b)
        elif -c <= d and -a > b:
            if a*c > b*d:
                print(a*c)
            elif a*c <= b*d:
                print(b*d)
        elif -c > d and -a <= b:
            if a*c > b*d:
                print(a*c)
            elif a*c <= b*d:
                print(b*d)
        elif -c > d and -a > b:
            print(a*c)
    elif c> 0 and d > 0:
        print(b*d)
    elif c<=0 and d<=0:
        print(a*c)

Measured memory_bytes: 9140
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=998244353;
ll A,B,C,D;
ll DP[3001][3001][2][2];

int main(){
	cin>>A>>B>>C>>D;
	DP[A][B][1][1]=1;
	for(int i=A;i<=C;i++){
		for(int j=B;j<=D;j++){
			DP[i][j][0][0]=(DP[i-1][j-1][0][0]+DP[i-1][j-1][0][1]+DP[i-1][j-1][1][0]+DP[i-1][j-1][1][1])*(i-1)*(j-1)%mod;
			DP[i][j][1][0]=(DP[i-1][j][0][0]+DP[i-1][j][0][1]+(DP[i-1][j][1][0]+DP[i-1][j][1][1])*j)%mod;
			DP[i][j][0][1]=(DP[i][j-1][0][0]+DP[i][j-1][1][0]+(DP[i][j-1][0][1]+DP[i][j-1][1][1])*i)%mod;
		}
	}
	cout<<(DP[C][D][0][0]+DP[C][D][0][1]+DP[C][D][1][0]+DP[C][D][1][1])%mod<<endl;
}


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

#define repo(i,n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;

int main(){

    array<int, 32> s = {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};
    int K;
    cin >> K;

    cout << s.at(K-1) << endl;

    return 0;
}



Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = Integer.parseInt(sc.next());
        int W = Integer.parseInt(sc.next());
        int D = Integer.parseInt(sc.next());
        int[][] A = new int[H][W];
        int[][] inv_A = new int[H*W+1][2];
        for (int i=0;i<H;i++) {
            for (int j=0;j<W;j++) {
                A[i][j] = Integer.parseInt(sc.next());
                inv_A[A[i][j]][0] = i;
                inv_A[A[i][j]][1] = j;
            }
        }
        long[][] dp = new long[D][H*W/D+1];
        for (int i=0;i<D;i++) {
            for (int j=0;j<H*W/D;j++) {
                if ((D*(j+1)+i+1)<=H*W) {
                    dp[i][j+1] = dp[i][j] + Math.abs(inv_A[D*(j+1)+i+1][0]-inv_A[D*j+i+1][0]) + Math.abs(inv_A[D*(j+1)+i+1][1]-inv_A[D*j+i+1][1]);
                }
            }
        }
        // System.out.println(Arrays.deepToString(dp));

        int Q = Integer.parseInt(sc.next());
        for (int i=0;i<Q;i++) {
            int L = Integer.parseInt(sc.next());
            int R = Integer.parseInt(sc.next());
            System.out.println(dp[(R-1)%D][(R-1)/D]-dp[(L-1)%D][(L-1)/D]);
        }
    }
}

Measured memory_bytes: 77428
#include<bits/stdc++.h>
#define ll long long

using namespace std;

struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
    Node(int x)
    {
        data=x;
        left=NULL;
        right=NULL;
    }
};
#define Node struct Node

ll modpow(ll a, ll n)
{
    ll m=1e9+7;
    if(n==0)
        return 1;
    ll y=modpow(a,n/2)%m;
    if(n%2==0)
        return (y*y)%m;
    return (((y*y)%m)*a)%m;
}

int main()
{
    int t=1;
    //cin>>t;
    while(t--)
    {
        ll m=1e9+7;
        ll n;
        cin>>n;
        cout<<(modpow(10,n)-2*modpow(9,n)+modpow(8,n)+2*m)%m<<endl;
    }
    return 0;
}







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

int main()
{
	std::map<string, int> itemCountMap;

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		string name;
		cin >> name;

		if(itemCountMap.find(name) == itemCountMap.end()){
			itemCountMap[name] = 1;
		}else{
			itemCountMap[name]++;
		}
		

	}

	cout << itemCountMap.size() << endl;
	return 0;
}

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

int main() {
  int n;
  cin>>n;
  int x=0;
  int Ncopy=n;
  while (n>0){
    x+=n%10;
    n/=10;
    }
  if (Ncopy%x==0)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
      }

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using static System.Math;


namespace AtCodeeeer
{
    class AtCOOOOOOOOOOOder
    {
        static void Main(string[] args)
        {
            List<int> ls = new List<int>();
            ls.Add(int.Parse(ReadLine()));
            ls.Add(int.Parse(ReadLine()));
            ls.Add(int.Parse(ReadLine()));
            ls.Add(int.Parse(ReadLine()));
            ls.Add(int.Parse(ReadLine()));
            int k = int.Parse(ReadLine());
            WriteLine((ls.Max() - ls.Min()) <= k ? "Yay!" : ":(");
        }
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    int M1, D1, M2, D2;
    cin >> M1 >> D1 >> M2 >> D2;
    cout << (M1 == M2 ? 0 : 1) << endl;
    return 0;
}

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

int main(void){
    int a, b, c;
    cin >> a >> b >> c;
    
    int x, y, z;
    x = a * 10 + b + c;
    y = a + b * 10 + c;
    z = a + b + c * 10;
    
    cout << max(x, max(y, z)) << endl;
}


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

int main(){
    int n; cin >> n;
    int a[n];

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

    for(int i = 0; i < n; i++){
        int v = a[i];
        int j = i-1;
        while(j>=0 && a[j]>v){
            a[j+1]=a[j];
            j--;
            a[j+1]=v;
        }
        
        for(int i = 0; i < n; i++){
            if(i<n-1){
                cout << a[i] << " ";
            }else{
                cout << a[i] << endl;
            }
        }
    }
}


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

template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }
    
    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }
    
    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N,Q; cin >> N >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
	vector<int> lefts(Q), rights(Q), ids(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> lefts[i] >> rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return rights[i] < rights[j];});

    BIT<int> bit(N+5);
    vector<int> prev(1100000, -1);
    vector<int> res(Q, 0);
    int r = 0;
    for (auto i : ids) {
        for (; r < rights[i]; ++r) {
            bit.add(prev[a[r]]+2, r+2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i]+1, lefts[i]+2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}

Measured memory_bytes: 21724
# AtCoder Beginner Contest 075
# B - Minesweeper
# https://atcoder.jp/contests/abc075/tasks/abc075_b
H, W, *S = open(0).read().split()
H, W = int(H), int(W)
S = [tuple(s) for s in S]

ans = [[0]*W for _ in [0]*H]
dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

for y, _s in enumerate(S):
    for x, s in enumerate(_s):
        if s == '#':
            ans[y][x] = '#'
            for dy, dx in dirs:
                if 0 <= x + dx < W and 0 <= y + dy < H and S[y+dy][x+dx] != "#":
                    ans[y+dy][x+dx] += 1

for a in ans:
    print(''.join(map(str, a)))


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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

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

const int N = 2e5 + 5;

int A[N], B[N];

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> A[i], B[i] = A[i];
	sort(B, B + n);
	for (int i = 0; i < n; i++) {
		if (A[i] < B[n / 2]) cout << B[n / 2] << endl;
		else cout << B[n / 2 - 1] << endl;
	
	}

	return 0;
}


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

#define boost ios::sync_with_stdio(0); cin.tie(0);
#define int long long

const int N = 1e5 + 10;
string a;
string b;

int32_t main(){
	boost;

	for(int i = 0 ; i < N ; ++i){
		if(i%2){
			a += '1';
			b += '0';
		}
		else{
			b += '1';
			a += '0';
		}
	}
	
	string s;

	cin >> s;
	int c = 0, d = 0;
	for(int i = 0 ; i < s.length() ; ++i){
		if(s[i] != a[i]){
			++c;
		}
		if(s[i] != b[i]){
			++d;
		}
	}

	cout << min(c,d);
	return 0;
}

Measured memory_bytes: 768
import java.util.*;

public class Main {


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        int k = sc.nextInt();
        int[][] g = new int[r][c];
        for(int i=0; i<k ;i++) {
            int x = sc.nextInt() -1;
            int y = sc.nextInt() -1;
            int v = sc.nextInt();
            g[x][y] = v;
        }
        long[][][] dp = new long[r][c][4];
        if(g[0][0]>0) {
            dp[0][0][1] = g[0][0];
        }
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                for(int q=0; q<=3; q++) {
                    if(j+1<c) {
                        dp[i][j+1][q] = Math.max(dp[i][j+1][q],dp[i][j][q]);
                        if(g[i][j+1]>0 && q<3) {
                            dp[i][j+1][q+1] = Math.max(dp[i][j+1][q+1], dp[i][j][q]+g[i][j+1]);
                        }
                    }
                    if(i+1<r) {
                        dp[i+1][j][0] = Math.max(dp[i+1][j][0],dp[i][j][q]);
                        if(g[i+1][j]>0) {
                            dp[i+1][j][1] = Math.max(dp[i+1][j][1], dp[i][j][q]+g[i+1][j]);
                        }
                    }
                }
            }
        }
        long res = 0;
        for(int i=0; i<4; i++) {
            res = Math.max(res, dp[r-1][c-1][i]);
        }
        System.out.println(res);


    }
}

Measured memory_bytes: 702696
def main():
    s = [int(item) for item in input().split()]
    _, _, X, Y = s
    xs = [int(item) for item in input().split()]
    ys = [int(item) for item in input().split()]
    mx = max(xs)
    my = min(ys)
    if mx >= Y:
        print('War')
        return
    if my <= X:
        print('War')
        return
    if mx >= my:
        print('War')
        return
    print('No War')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <math.h>
#include <map>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int sum = 0;

int main() {
	int N; cin >> N;
	vector<int> V(N), C(N);
	for (int i = 0; i < N; i++) {
		cin >> V.at(i);
	}
	for (int i = 0; i < N; i++) {
		cin >> C.at(i);
	}
	for (int i = 0; i < N; i++) {
		int a = V[i] - C[i];
		if (a > 0) sum += a;
	}
	
	cout << max(0, sum) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < (n); i++)
int main()
{
  int n;
  cin >> n;
  ll sum = 0;
  for (int i = 1; i <= n; i++)
  {
    ll y = n / i;
    sum += y * (y + 1) * i / 2;
  }
  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
// #define cerr if(false)cerr
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> ii;
typedef vector<vector<ll>> vvll;
typedef vector<pair<ll, ll>> vii;
typedef long double ld;
typedef vector<ld> vld;
typedef vector<vector<ld>> vvld;
typedef vector<bool> vbl;
typedef vector<vbl> mbl;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(s) (s).begin(), (s).end()
const ll MOD = 1e9 + 7;

inline void solve()
{
    ll n;
    cin >> n;
    ll ans = n;
    n++;
    for (int i = 2; i < n; i++)
    {
        ll u, v;
        cin >> u >> v;
        ans += i * (n - i) - min(u, v) * (n - max(u, v));
    }
    cout << ans << endl;
}

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

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 3536
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cmath>
#include<deque>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<tuple>
#include<utility>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<int>> vvi;

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define REP(i, n)  for(int i=0; i<(int)(n); i++)
#define REPS(i, n)  for(int i=1; i<=(int)(n); i++)
#define PER(i, n) for(int i=(int)(n)-1; i>= 0; i--)
#define PERS(i, n)  for(int i=(int)(n); i>0; i--)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i!=(c).end(); i++)
#define RFOR(i, c)  for(__typeof((c).rbegin()) i=(c).rbegin(); i!=(c).end(); i++)
#define ALL(container)  (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) (container).size()
#define FILL0(n)  setfill('0') << right << setw(n)
#define mp(a, b)  make_pair(a, b)
#define toLower(c)  c+0x20
#define toUpper(c)  c-0x20
#define pb  push_back
#define eb  emplace_back

const int INF = 1e9;
const long long LLINF = 1e18;
const int MOD = 1000000007;

int main(){
  int n;  cin >> n;
  vi a(n+1, 0), box(n+1, 0), res;
  int in=0;
  REPS(i, n) cin >> a[i];
  PERS(i, n){
    int cnt = 0;
    for(int j=i; j<=n; j+=i){
      cnt ^= box[j];
    }
    if(cnt != a[i])  {
      box[i]=1;
      res.push_back(i);
    }
  }
  cout << res.size() << endl;
  REP(i, res.size()){
    if(i>0)cout << " ";
    cout << res[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a, b;
  cin >> a >> b;
  int c;
  c = (a*b)/2;
  if( a*b == c*2){
    cout << "Even" << endl;
  }
  else{
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
n, a, b = [ int(v) for v in input().split() ]
if n == 1:
    if a != b:
        ans = 0
    else:
        ans = 1
else:
    if a <= b:
        maxsum = a + b*(n-1)
        minsum = a*(n-1) + b
        ans = maxsum - minsum + 1

    else:
        ans = 0
print(ans)

Measured memory_bytes: 38384
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size,n=1,init=nil) #nに配列の次元数、sizeに配列の大きさ、initに初期値を投げることでその配列を返す
  if n==1
    return Array.new(size){init}
  else
    return Array.new(n).map{Array.new(size){init}}
  end
end
n,a,b=get_i
i=n/(a+b)
r=n% (a+b)
ans=a*i
if r<a
  ans+=r
else
  ans+=a
end
puts ans

Measured memory_bytes: 3836
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
const int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30);
const int INF = (1LL << 60);
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}

struct UnionFind {
  private:
  vector<int> child,tree;
  vector<vector<int>> list;

public:
  UnionFind(int v) {
    tree.resize(v);
    list.resize(v);
    REP(i,v) tree[i] = i, list[i].push_back(i);
  }

  int root(int i){
    if(i == tree[i]){
      REP(j,child.size()) tree[child[j]] = i;
      child.clear(); 
      return i;
    }
    else{
      child.push_back(i);
      return i = root(tree[i]);
    }
  }

  int size(int i){
    return list[root(i)].size();
  }

  vector<int> nodes(int no){
    return list[root(no)];
  }

  bool unit(int x, int y){
    x = root(x);
    y = root(y);
    if(x==y) return false;
    if(list[x].size() < list[y].size()) swap(x,y);
    for(int no:list[y]) list[x].emplace_back(no);
    tree[y] = x;
    return true;
  }

  bool isUnit(int x, int y){
    return root(x) == root(y);
  }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    int n,m;
    cin>>n>>m;
    UnionFind uf(n);
    pvec ab(m);
    rep(i,m) cin>>ab[i].fs>>ab[i].sc;
    reverse(all(ab));
    vec ans(m);
    rep(i,m){
        ab[i].fs--;ab[i].sc--;
        if(uf.isUnit(ab[i].fs,ab[i].sc)){
            ans[i]=0;
        }
        else{
            ans[i]=uf.size(ab[i].fs)*uf.size(ab[i].sc);
        }
        uf.unit(ab[i].fs,ab[i].sc);
    }
    reverse(all(ans));
    cout<<ans[0]<<endl;
    rep(i,m-1){
        ans[i+1]+=ans[i];
        cout<<ans[i+1]<<endl;
    }
    
}

Measured memory_bytes: 17648
//29
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  for(int n,m;cin>>n>>m,n|m;){
    int t[20001]={};
    for(int i=0;i<n+m;i++){
      cin>>t[i+1];
    }
    sort(t,t+n+m+1);
    int mi=0;
    for(int i=1;i<n+m+1;i++){
      mi=max(mi,t[i]-t[i-1]);
    }
    cout<<mi<<endl;
  }
  return 0;
}

Measured memory_bytes: 948
A,B,K=gets.split.map(&:to_i)
an=[]
K.times{|i|
  break if i+A>B
  an.push(i+A)
}
K.times{|i|
  break if B-i<A
  an.push(B-i) if !an.include?(B-i)
}
an.sort!
an.each{|a|puts a}

Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define N 200005
#define ls x<<1,l,mid
#define rs x<<1|1,mid+1,r
#define int long long
using namespace std;
int n,q,ps;
int w[N];
int a[N*4],b[N*4],lazy[N*4];
void push_down(int x)
{
    int l=x*2,r=x*2+1,z=lazy[x];
    a[l]+=z;b[l]+=z;
    a[r]+=z;b[r]+=z;
    lazy[l]+=z;lazy[r]+=z;
    lazy[x]=0;
}
void push_up(int x)
{
    a[x]=min(a[x<<1],a[x<<1|1]);
    b[x]=min(b[x<<1],b[x<<1|1]);
}
int qur1(int x,int l,int r,int ll,int rr)
{
    if(l>=ll&&r<=rr)return a[x];
    push_down(x);
    int mid=(l+r)>>1;
    if(ll>mid)return qur1(rs,ll,rr);
    if(rr<=mid)return qur1(ls,ll,rr);
    return min(qur1(ls,ll,rr),qur1(rs,ll,rr));
}
int qur2(int x,int l,int r,int ll,int rr)
{
    if(l>=ll&&r<=rr)return b[x];
    push_down(x);
    int mid=(l+r)>>1;
    if(ll>mid)return qur2(rs,ll,rr);
    if(rr<=mid)return qur2(ls,ll,rr);
    return min(qur2(ls,ll,rr),qur2(rs,ll,rr));
}
void add(int x,int l,int r,int pos,int z)
{
    if(l==r)
    {
        a[x]=min(a[x],z-l);
        b[x]=min(b[x],z+l);
        return ;
    }
    int mid=(l+r)>>1;
    push_down(x);
    if(pos<=mid)add(ls,pos,z);
    else add(rs,pos,z);
    push_up(x);
}
int ans=1LL<<60;
void dfs(int x,int l,int r)
{
    if(l==r)
    {
        ans=min(ans,b[x]-l);
        return ;
    }
    int mid=(l+r)>>1;
    push_down(x);
    dfs(ls);dfs(rs);
}
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&q,&w[0],&ps);
    memset(a,0x3f,sizeof(a));memset(b,0x3f,sizeof(b));add(1,1,n,ps,0);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&ps);w[i]=ps;
        int tmp=min(qur2(1,1,n,ps,n)-ps,ps+qur1(1,1,n,1,ps));
        int tp=abs(ps-w[i-1]);
        lazy[1]+=tp;a[1]+=tp;b[1]+=tp;
        add(1,1,n,w[i-1],tmp);
    }
    dfs(1,1,n);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 20608
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <iomanip>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
using namespace std;
#define double long double
#define int long long
#define low lower_bound
#define upp upper_bound
#define mod (int)1e9+7
#define inf (int)1e16
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout<<endl;
#define prique(T) priority_queue<T,vector<T>,greater<T>>
struct edge { int to, cost; };
typedef pair<int, int> P;

signed main() {
	string s;
	cin >> s;
	int o = 0;
	rep(i, s.size()) if (s[i] == 'o') o++;
	if (8 <= o+15-s.size()) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a, b, c, d;
  cin>>a>>b>>c>>d;
  if(a+b>c+d){
    cout<<"Left"<<endl;
  }
  else if(a+b==c+d){
    cout<<"Balanced"<<endl;
  }
  else{
    cout<<"Right"<<endl;
  }
}


Measured memory_bytes: 256
/*

    HARSH KHATRI
    DA-IICT     

		 */

           	 

#include <bits/stdc++.h>

#define LOCAL 0
bool debug = true;

using namespace std;

int main(void) {
	
	if(LOCAL) {
    	freopen("in.txt", "r", stdin);
	    freopen("out.txt", "w", stdout);
	}

	int i, j, k, n, m;
	string s, t;
	cin >> s >> t;
	n = s.size(); m = t.size();
	if(n!=m) { printf("No\n"); return 0; }

	s += s;
	for(i=0; i<n; i++) {
	 	bool same = true;
		for(j=0; j<n; j++) {
		 	if(s[j+i]!=t[j]) { same = false; break; }
		}
		if(same) { printf("Yes\n"); return 0; }
	}

	printf("No\n"); 
	return 0;	
}

Measured memory_bytes: 256
n = int(input())
s = input()
dp = [1] * n
mod = 10 ** 9 + 7
for ind, i in enumerate(s):
    dp2 = [0] * n
    if i == ">":
        s = 0
        for j in reversed(range(n-ind)):
            dp2[j] = s
            s += dp[j]
            s %= mod
    else:
        s = 0
        for j in range(n):
            s += dp[j]
            dp2[j] = s
            s %= mod
    dp = dp2
print(dp[0])

Measured memory_bytes: 43100
s = input()

g = set()
for i in s:
    g.add(i)

al = [chr(ord('a') + i) for i in range(26)]
a = 'abcdefghijklmnopqrstuvwxyz'

if s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
elif len(s) < 26:
    for w in al:
        if w in g:
            continue
        s += w
        print(s)
        break
else:
    for i in reversed(range(26)):
        j = a.find(s[i])
        g.remove(a[j])
        while j < 25:
            j += 1
            s = s[:-1] + a[j]
            if not a[j] in g:
                print(s)
                exit()
        s = s[:-1]

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<string>

using namespace std;

int main() {
    string str, str1, str2;
    int m, h;
    while (true) {
        cin >> str;
        if (str == "-") break;
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> h;
            str1 = str.substr(0, h);
            str2 = str.substr(h, str.size()-h);
            str = str2 + str1;
        }
        cout << str << endl;
    }
    return 0;
}


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

#define int long long

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

  int R, G, B, N;
  cin >> R >> G >> B >> N;

  int ans = 0;
  for ( int i = 0; i <= N; i++ ) {
    for ( int j = 0; j <= N; j++ ) {
      if ( (i*R+j*G) <= N && (N-(i*R+j*G))%B == 0 ) ans++;
    }
  }

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


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

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

  int N=in(),M=in();
  vector<int> X(M),Y(M-1);
  for(auto& x:X) x=in();
  sort(ALL(X));
  for(int i=0;i<M-1;i++){
    Y[i]=X[i+1]-X[i];
  }
  sort(ALL(Y));
  
  int num = min(N-1,M-1);
  cout << accumulate(Y.begin(),Y.end()-num,0) << endl;
  return 0;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/02/15  Problem: 061_abc_d / Link: https://abc061.contest.atcoder.jp/tasks/abc061_d?lang=en  ----- */
/* ------問題------

N 頂点 M 辺の重み付き有向グラフがあります。 
i(1≦i≦M) 番目の辺は 頂点 ai から 頂点 bi を重み ci で結びます。 
このグラフと駒を利用して、次の1人ゲームを行います。

最初、駒を頂点 1 に置いて、プレイヤーのスコアを 0 とします。 
プレイヤーは、次の条件で駒を繰り返し移動させることができます。

頂点 ai に駒があるとき、i 番目の辺を利用して頂点 bi に移動する。移動後にプレイヤーのスコアが ci 加算される。
頂点 N に駒があるときのみ、ゲームを終了できます。 
なお、与えられる有向グラフの上で頂点 1 から頂点 N に移動できることは保障されています。

プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか? 
ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。

-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */


struct Edge {
	LL to, cost;
	Edge(int t, LL c = 0) : to(t), cost(c)
	{}
	bool operator>(const Edge& rhs) const {
		return cost > rhs.cost;
	}
	bool operator<(const Edge& rhs) const {
		return cost < rhs.cost;
	}

};
using Graph = vector< vector<Edge> >;


// precondition: d.size == V
// O(V*E)
// 負閉路が存在するときはfalse,そうでないときはtrue
void BellmanFord(const Graph& G, vector<LL>& d) {
	const int V = G.size();
	//for (int i = 0; i < V; ++i)
	//	d[i] = INF;
	//d[s] = 0;

	for (int lp = 0; lp <= V; ++lp) {
		for (int i = 0; i < V; ++i) {
			for (const auto& e : G[i]) {
				if ( d[e.to] < d[i] + e.cost) {
					d[e.to] = d[i] + e.cost;
				}
			}
		}
	}
}



LL N,M;

LL ans = 0LL;

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

	cin >> N>>M;
	Graph G(N);
	FOR(i, 0, M) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		G[a].push_back(Edge(b,c));
	}
	VL dist(N, -LINF);
	dist[0] = 0;
	BellmanFord(G, dist);
	VL d2 = dist;
	BellmanFord(G, d2);

	if (d2[N - 1] != dist[N - 1]) {
		cout << "inf" << endl;
	}else
	{
		ans = dist[N - 1];
		cout << ans << "\n";
	}

	return 0;
}


Measured memory_bytes: 384
#include<complex>
#include<cstdio>
#include<cmath>
using namespace std;
typedef complex<double> P;
double F(double a,double b,double c){
	return acos((b*b+c*c-a*a)/(2*b*c));
}
int main(){
	int n;
	double d,e,f,g,h,i;
	for(scanf("%d",&n);n--;){
		scanf("%lf%lf%lf%lf%lf%lf",&d,&g,&e,&h,&f,&i);
		P a(d,g),b(e,h),c(f,i);
		double A=abs(b-c),B=abs(c-a),C=abs(a-b),
		s=sin(2*F(A,B,C)),t=sin(2*F(B,C,A)),u=sin(2*F(C,A,B)),v=s+t+u;
		printf("%.3f %.3f %.3f\n",(d*s+e*t+f*u)/v,(g*s+h*t+i*u)/v,A/sin(F(A,B,C))/2.);
	}
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int MOD = 1e9+7, MAX = 1e9, larg = 1e5, INF = -1e9;
long long A,B,C,D,E,F,G,H,I,J,K,L,N,M,O,P,Q,R,S,T,U,V,W,X,Y,Z;
long long max_value = 0, max_index = 0;
long long min_value = MAX, min_index = 0;
long long sum = 0;

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

int main() {
    cin >> A >> B;
    if((A*B)%2 == 1) cout << "Yes";
    else cout << "No";
}

Measured memory_bytes: 256
n = int(input())

old = None
w = []

for i in range(n):
    word = input()
    if old:
        if word[0] != old[-1]:
            print("No")
            exit()
        elif word in w:
            print("No")
            exit()
    w.append(word)
    old = word
    print()

print("Yes")

Measured memory_bytes: 3060
fn main() {
    proconio::input! {
        n: proconio::marker::Chars,
    }

    let mut r = 0;
    for ni in n {
        r = (r + ni.to_digit(10).unwrap()) % 9;
    }
    dbg!(r);
    println!("{}", if r == 0 {"Yes"} else {"No"});
}


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

bool a[200010], b[200010];

int main() {
	int n, m, x, y;
	a[0] = false;
	b[0] = false;

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		if (x == 1) {
			a[y] = 1;
		}
		if (y == n) {
			b[x] = 1;
		}
	}

	for (int i = 2; i <= n; i++) {
		if (a[i] == 1 && b[i] == 1) {
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;
	return 0;
}

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

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

    int n;
    cin >> n;
    vector<long long> A(n);
    REP(i, n) cin >> A[i];

    long long cost = 0;
    REP(i, n){
        if(i == 0 or i == n - 1){
            cost += abs(A[i]);
        }
        if(i < n - 1){
            cost += abs(A[i + 1] - A[i]);
        }
    }
    
    REP(i, n){
        long long tmp = cost;
        if(i == 0){
            if((0 <= A[i] and A[i] <= A[i + 1]) or (0 >= A[i] and A[i] >= A[i + 1]));
            else tmp = tmp - (abs(A[i]) + abs(A[i + 1] - A[i])) + abs(A[i + 1]);
        }else if(i == n - 1){
            if((A[i - 1] <= A[i] and A[i] <= 0) or (A[i - 1] >= A[i] and A[i] >= 0));
            else tmp = tmp - (abs(A[i] - A[i - 1]) + abs(A[i])) + abs(A[i - 1]);
        }else{
            if((A[i - 1] <= A[i] and A[i] <= A[i + 1]) or (A[i - 1] >= A[i] and A[i] >= A[i + 1]));
            else tmp = tmp - (abs(A[i + 1] - A[i]) + abs(A[i] - A[i - 1])) + abs(A[i + 1] - A[i - 1]);
        }
        cout << tmp << endl;
    }

    return 0;
}


Measured memory_bytes: 2048
s = gets.chomp
k = gets.to_i
n = s.size


substr = "zzzzz"

n.times do |i|
    break if i + k > n
    substr = s[i, k] if substr >= s[i, k]
end

ary = []
k.times {|i| ary << substr[0..i]}

([n - k + 1, 0].max).upto(n - 1) do |i|
    i.upto(n - 1) do |j|
        ary << s[i..j]
    end
end

puts ary.uniq.sort[k - 1]

Measured memory_bytes: 1788
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N := ReadInt()
	dp := make([]int, N+1)
	for i := 1; i <= N; i++ {
		dp[i] = 1 + dp[i-1]
		for p := 6; p <= i; p *= 6 {
			dp[i] = Min(dp[i], 1+dp[i-p])
		}
		for p := 9; p <= i; p *= 9 {
			dp[i] = Min(dp[i], 1+dp[i-p])
		}
	}
	fmt.Println(dp[N])
}

func Min(xs ...int) int {
	min := xs[0]
	for _, x := range xs[1:] {
		if min > x {
			min = x
		}
	}
	return min
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) (a []int) {
	for i := 0; i < n; i++ {
		a = append(a, ReadInt())
	}
	return
}


Measured memory_bytes: 2648
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
ll mod;


vector<ll> inv,fact,invfact;
void mod_build(int n=101010){
	fact.resize(n+1);
	inv.resize(n+1);
	invfact.resize(n+1);
	fact[0]=inv[0]=invfact[0]=1;
	inv[1]=1;
	rep(i,n){
		fact[i+1]=fact[i]*(i+1)%mod;
		if(i>0)inv[i+1]=mod-inv[mod%(i+1)]*(mod/(i+1))%mod;
		invfact[i+1]=invfact[i]*inv[i+1]%mod;
	}
}
ll perm(int n,int k){
	if(n<0||k<0||k>n)return 0;
	return fact[n]*invfact[n-k]%mod;
}
ll comb(int n,int k){
	if(n<0||k<0||k>n)return 0;
	return (fact[n]*invfact[n-k]%mod)*invfact[k]%mod;
}
ll powmod(ll n,ll k){
	ll ret=1;
	while(k){
		if(k&1)ret=ret*n%mod;
		n=n*n%mod;
		k>>=1;
	}
	return ret;
}
int main(){
	ll n;
	cin>>n>>mod;
	mod_build(101010);
	ll ans=0;
	for(int i=1;i<=n-1;++i){
		ll res=0;
		for(int j=0;j<=i;++j){
			if(j%2)res+=comb(i,j)*(mod-powmod(powmod(2,(i-j))-1,n-i))%mod;
			else res+=comb(i,j)*powmod(powmod(2,(i-j))-1,n-i)%mod;
		}
		res%=mod;
		res=res*comb(n,i)%mod;
		ans+=res*powmod(2,(n-i)*(n-i-1)/2)%mod*powmod(2,i*(i-1)/2)%mod;
	}
	cout<<ans%mod<<endl;
	return 0;
}


Measured memory_bytes: 5216
// 177

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>
#include <iomanip>
#include <climits>
#include <string>
#include <cmath>

using namespace std;
using ll = long long int;
#define NUM 1000000007

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


Measured memory_bytes: 3632
#include<bits/stdc++.h>
    #define ll long long int
    #define ull unsigned long long 
    #define ff first
    #define ss second
    #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #define pb push_back 
    #define mp make_pair
    #define inf 2000000009
    #define mod 1000000007
    using namespace std;
     
    int main()
    { 
      fast;
       ll n,w;
       cin>>n>>w;
     
       ll wt[n],val[n];
       for(ll i=0;i<n;i++)
       	cin>>wt[i]>>val[i];
     
       ll dp[w+1];
     	memset(dp,0,sizeof(dp));

       for(ll i=0;i<n;i++)
       	for(ll j=w;j>-1;j--)
       	{
       		 if(wt[i]<=j)
       				dp[j]=max(dp[j],dp[j-wt[i]]+ val[i]);
       	}

       cout<<*max_element(dp,dp+w+1)<<endl;
    }

Measured memory_bytes: 1024
N = int(input())
c = [[0]*10 for _ in range(10)]
for k in range(1,N+1):
    k = str(k)
    i = int(k[0])
    j = int(k[-1])
    c[i][j] +=1
ans=0
for i in range(10):
    for j in range(10):
        ans += c[i][j] * c[j][i]

print(ans)

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

#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef vector<int> vi;

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

	int n;
	cin >> n;
	vector<double> v(n);
	rep(i, n){
		cin >> v[i];
	}

	sort(all(v));

	double ans = v[0];
	rept(i, 1, n){
		ans = (ans + v[i]) / 2.0;
	}

//	cout << fixed;	
	cout << setprecision(6) << ans << endl;


    return 0;
}



Measured memory_bytes: 256
class SegmentTree:

    def __init__(self, n, fn=lambda x, y: min(x, y), unity=(1 << 31) - 1):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.arr = [unity] * (2 * self.n - 1)
        self.fn = fn
        self.unity = unity

    def update(self, i, x):
        k = self.n + i - 1
        self.arr[k] = x

        while k > 0:
            k = (k - 1) // 2
            self.arr[k] = self.fn(self.arr[2 * k + 1], self.arr[2 * k + 2])

    def query(self, l, r):
        return self._inner_query(l, r, 0, 0, self.n)

    def _inner_query(self, l, r, k, il, ir):
        if ir <= l or r <= il:
            return self.unity

        elif l <= il and ir <= r:
            return self.arr[k]

        vl = self._inner_query(l, r, k * 2 + 1, il, (il + ir) // 2)
        vr = self._inner_query(l, r, k * 2 + 2, (il + ir) // 2, ir)
        return self.fn(vl, vr)

    def __str__(self):
        return self.arr[0: 2 * self.n].__str__()

n, q = map(int, input().split())
st = SegmentTree(n)

for _ in range(q):
    com, o1, o2 = map(int, input().split())

    if com == 0:
        st.update(o1, o2)
    else:
        print(st.query(o1, o2 + 1))



Measured memory_bytes: 8696
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
double PI=3.14159265359;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double a,b,h,m;cin>>a>>b>>h>>m;
    double xn=a*sin((60*h+m)*PI*2.0/720.0);
    double yn=a*cos((60*h+m)*PI*2.0/720.0);
    double xl=b*sin(m*PI*2.0/60.0);
    double yl=b*cos(m*PI*2.0/60.0);
    double norm=pow((xn-xl),2.0)+pow((yn-yl),2.0);
    cout<<fixed<<setprecision(12)<<pow(norm,0.5)<<endl;
    return 0;
}


Measured memory_bytes: 4208
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
//#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define bp __builtin_popcount
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD = 1e9 + 7;
//const int INF = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>void print(T t){for(auto &it : t)cout<<it<<" ";}
inline int powerexp(int a, int b, int m = MOD){ int res = 1;while(b){if(b&1)res = res * a % m;a = a * a % m,b >>= 1;}return res % m;}
inline int modinv(int a){ return powerexp(a,MOD-2,MOD);}
inline int lcm(int a, int b){ int g = __gcd(a,b);return a/g*b;}
inline int add(int x, int y){ x += y; if (x >= MOD) x -=  MOD; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % MOD;}
inline int sub(int x, int y){ x -= y; if (x<0) x += MOD; return x ;}

//-------------------< start here >-------------------------// 

void solve(){
   string s;
   getline(cin , s);
   for(int i = 0; i + 4 < (int)s.length(); i++){
	   if (s[i] == 'a' && s[i + 1] == 'p' && s[i + 2] == 'p' && s[i + 3] == 'l' && s[i + 4] =='e'){
		   s[i] = 'p', s[i + 1] = 'e', s[i + 2] = 'a', s[i + 3] = 'c', s[i + 4] = 'h';   
		 }
	   else if (s[i] == 'p' && s[i + 1] == 'e' && s[i + 2] == 'a' && s[i + 3] == 'c' && s[i + 4] =='h'){
		   s[i] = 'a', s[i + 1] = 'p', s[i + 2] = 'p', s[i + 3] = 'l', s[i + 4] = 'e';   
		 }   
	 }
	cout << s << endl;    
}

//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   //find();
   #ifdef LOCAL_DEFINE
   cerr << "time elapsed " << (double)clock()/CLOCKS_PER_SEC << endl;
   #endif
}



Measured memory_bytes: 3116
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
static const int NMAX = 100000;
int main() {
	int L[NMAX], A[NMAX];
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	int length = 1;
	L[0] = A[0];
	for (int i = 1; i < n; i++) {
		if (L[length-1] < A[i]) {
			L[length++] = A[i];
		}
		else {
			*lower_bound(L, L + length, A[i]) = A[i];
		}
	}
	cout << length << endl;
}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
#ifdef DEBUG
#include "_debug.cpp"
#include "callable.hpp/callable.hpp"
#endif
#define endl '\n'
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    cout << (1 << m) * ((n - m) * 100 + m * 1900) << endl;
    return 0;
}


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

sorted_x = sorted(X)
low_mid = sorted_x[N//2-1]
high_mid = sorted_x[N//2]

for x in X:
    if x < high_mid:
        print(high_mid)
    else:
        print(low_mid)


Measured memory_bytes: 25620
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <functional>

using namespace std;
using ll = long long;

#define FOR(i, m, n) for(int i = (m);i < (n);i++)
#define REP(i,n) for(int i = 0; i < int(n); i++)
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VL vector<ll>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define PAIR pair<int,int>
#define MP make_pair
#define VP vector<pair<int,int>>
#define VS vector<string>
#define QUE queue<int>
#define DEQ deque<int>
#define PQUE priority_queue<int> //5,5,4,3,3,2,...
#define REPQUE priority_queue<int, vector<int>, greater<int>> //1,1,2,3,4,4,5,...
#define SUM(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SORT(obj) ((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) ((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n

const ll MOD = (ll)1e9 + 7;

int bfs(int K);

int main() {
	int K;
	cin >> K;
	cout << bfs(K) << endl;
	return 0;
}

int bfs(int K) {
	VB node(K, true);
	deque<PAIR> que;
	que.push_back(PAIR(1, 1));

	while (!que.empty()) {
		int score = que.front().first;
		int position = que.front().second;
		int next_position;
		que.pop_front();
		if (position == 0) return score;

		node[position] = false;

		next_position = (position * 10) % K;
		if (node[next_position]) que.push_front(PAIR(score, next_position));

		next_position = (position + 1) % K;
		if (node[next_position]) que.push_back(PAIR(score + 1, next_position));
		
	}
}



Measured memory_bytes: 768