akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

#define NMAX 200000

int main(void){
	int n,c,i,j;
	int r[NMAX];
	scanf("%d",&n);
	for(c=0;c<n;c++){
		scanf("%d",&r[c]);
	}
	int maxj = -1000000000;
	int mini = r[0];
	for(j=1;j<n;j++){
		if(maxj < r[j] - mini){
			maxj = r[j] - mini;
		}
		if(mini > r[j]){
			mini = r[j];
		}
	}
	printf("%d\n",maxj);
}


Measured memory_bytes: 2580
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include <vector>

#include <bits/stdc++.h>
using namespace std;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define TRUE (0)
#define FALSE (1)

// This value shold be close to used maximum value.  
#define NUM_MAX 20000000005

// void sort(uint32_t *num, uint32_t size);

int main()
{
    vector<vector<uint64_t>> arr(0);
    vector<uint64_t> temp_vec(2);
    vector<uint64_t> num_vec(0);
    string result;
    // vector<long long> res_vec(0);
    // uint64_t res_arr[NUM_MAX];
    // uint32_t sum = 0;
    uint64_t num1, num2;
    uint64_t num;
    // uint64_t result;
    double length, mass;

    // uint32_t res_i = 0;
    // string str_temp, str_temp2;
    uint64_t temp, temp2;
    uint64_t i, j, k, l, count, n, o, size;
    // uint32_t count = 0;
    // string str;
    // uint8_t k_flag;
    
    cin >> num;

    num1 = num / 500;
    num2 = (num - (500 * num1)) / 5;

    num = num1 * 1000 + num2 * 5;

    cout << num << endl;
    // cout << fixed << setprecision(10) << mass << endl;

    // for (i=0; i<num; i++) {
    //     cin >> temp_vec.at(0) >> temp_vec.at(1);
    //     arr.push_back(temp_vec);
    // }

    // for (i=0; i<num; i++) {
    //     temp = arr.at(i).at(0);
    //     result[temp] = arr.at(i).at(1);
    // }

    return 0;
}

uint64_t silver_fox(vector<vector<int64_t>>& monster_arr, uint64_t range, uint64_t attack, uint64_t count)
{
    int64_t life, pos, num;
    int64_t i, short_i;

    while (monster_arr.size() != 0) {
        pos = monster_arr[0][0];
        life = monster_arr[0][1];
        count++;
        short_i = 0;

        for (i = 0; i < monster_arr.size(); i++) {
            short_i++;
            if (monster_arr[i][0] < pos + range) {
                monster_arr[i][1] -= attack;
            } else {
                break;
            }
        }

        for (i = short_i - 1; i >= 0; i--) {
            if (monster_arr[i][1] <= 0) {
                monster_arr.erase(monster_arr.begin() + i);
            }
        }
    }

    return count;
}

// void sort(uint32_t *num, uint32_t size) {
//     uint32_t i, j, k;
//     uint32_t sorted_num;
//     uint32_t array[NUM_MAX] = {0};

//     for (i = 1; i < size + 1; i++) {
//         array[num[i - 1]]++;
//     }

//     sorted_num = 0;

//     for (i = 0; i < NUM_MAX; i++) {
//         for (j = 0; j < array[i]; j++) {
//             num[j + sorted_num] = i;
//         }
//         sorted_num += j;
//         j = 0;
//     }

//     return;
// }


Measured memory_bytes: 256
import os
import sys
import numpy as np

def solve(N, AB):
    mod = 10**9+7
    half = mod // 2 + 1
    G = [[0]*0 for _ in range(N+1)]
    for i in range(len(AB)):
        a, b = AB[i]
        G[a].append(b)
        G[b].append(a)
    P = [0] * (N+1)
    Size = [0] * (N+1)
    def dfs(v):
        # siz = 1
        # p = P[v]
        # for u in G[v]:
        #     if u != p:
        #         P[u] = v
        #         dfs(u)
        #         siz += Size[u]
        # Size[v] = siz
        st = [(v, 0)]
        while st:
            v, state = st.pop()
            p = P[v]
            if state == 0:
                st.append((v, 1))
                Size[v] = 1
                for u in G[v]:
                    if u != p:
                        P[u] = v
                        st.append((u, 0))
            else:
                Size[p] += Size[v]
    dfs(1)
    ans = 0
    Prob = [0]
    h = 1
    for i in range(202020):
        h = h * half % mod
        Prob.append(1-h)
    for v in range(1, len(G)):
        siz_v = Size[v]
        Gv = G[v]
        if v == 1:
            ps = [0]*0
        else:
            ps = [Prob[N-siz_v]]
        par = P[v]
        for u in Gv:
            if par != u:
                siz_u = Size[u]
                ps.append(Prob[siz_u])
        if len(ps)<=1:
            continue
        cumprod1_ps = [1, 1]
        cumprod2_ps = [1, 1]
        cp = 1
        for p in ps:
            cp = cp * (1-p) % mod
            cumprod1_ps.append(cp)
        cp = 1
        for p in ps[::-1]:
            cp = cp * (1-p) % mod
            cumprod2_ps.append(cp)
        cumprod2_ps.reverse()
        an = 1 - cumprod1_ps[-1]
        for j in range(1, len(cumprod1_ps)-1):
            cp1 = cumprod1_ps[j]
            cp2 = cumprod2_ps[j]
            p = ps[j-1]
            an -= cp1 * cp2 % mod * p
        ans += an
    ans = ans % mod * half % mod
    return ans


def main():
    sys.setrecursionlimit(505050)
    input = sys.stdin.buffer.readline
    N = int(input())
    AB = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N - 1, 2)
    ans = solve(N, AB)
    print(ans)

main()


Measured memory_bytes: 87672
#include <iostream>
#include <algorithm>
using namespace std;
int z[100002],f[100002];
int main(){
    int n,max1=100001,max2=100001;
    cin>>n;
    int zheng[n/2],fan[n/2];
    for(int i=0;i<n;i++){
        if(i%2==0)cin>>zheng[i/2];
        if(i%2==1)cin>>fan[i/2];
    }
    bool flag=true,flag1=true,flag2=true;
    for(int i=0;i<n/2;i++){
        if(zheng[i]==fan[i] || (zheng[i]!=zheng[(i+1)%(n/2)] || fan[i]!=fan[(i+1)%(n/2)])){
            if(zheng[i]!=zheng[(i+1)%(n/2)])flag1=false;
            if(fan[i]!=fan[(i+1)%(n/2)])flag2=false;
            flag=false;
        }
    }
    if(flag){
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<n/2;i++){
        z[zheng[i]]++;
        f[fan[i]]++;
    }
    for(int i=0;i<=100000;i++){
        if(z[i]>z[max1])max1=i;
        if(f[i]>f[max2])max2=i;
    }
    sort(z,z+100001);
    sort(f,f+100001);
    if(max1==max2){
        if(flag1)cout<<n/2-f[99999]<<endl;
        else if(flag2)cout<<n/2-z[99999]<<endl;
        else cout<<n-max(z[100000]+f[99999],z[99999]+f[100000])<<endl;
    }else if(flag1)cout<<n/2-f[100000]<<endl;
    else if(flag2)cout<<n/2-z[100000]<<endl;
    else cout<<n-(z[100000]+f[100000])<<endl;
    return 0;
}


Measured memory_bytes: 1408
const main = stdin => {
  const input = stdin.trim().split('\n')

  const [H, W] = input[0].split(' ').map(x => parseInt(x))
  const [h, w] = input[1].split(' ').map(x => parseInt(x))

  console.log((H - h) * (W - w))
}
// 標準入力
main(require("fs").readFileSync("/dev/stdin", "utf8"))


Measured memory_bytes: 30604
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(a) cout << #a << ": " << a << endl
#define sz(a) int(a.size())
#define vi vector<int>
#define rep(i,n) for(int i=0;i<n;i++)
#define forr(i, st, en) for(int i = st; i <= en; i++)
#define all(v) (v).begin(),(v).end()
#define fast cin.tie(0); ios::sync_with_stdio(false)
#define int long long

int32_t main(){ fast;
               int k, n; cin>>n>>k;
               vector<int> a(n);
               rep(i, n){
                   cin>>a[i];
               }
               sort(all(a));
               int answer = 0;
               for(int i = 0; i < k; ++i){
                    answer += a[i];
               }
               cout<<answer<<endl;
}


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

int main()
{
    int a, b;
    cin >> a >> b;
    string s = string(b, '0' + a);
    string t = string(a, '0' + b);
    if (s < t)
        cout << s << endl;
    else
        cout << t << endl;
    return 0;
}

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


int main(){
    int n,m;cin>>n>>m;
    vector <int> x(m);
    int test= 0;
    rep(i,m){
        cin>>x[i];
    }
    sort(x.begin(),x.end());
    vector<int> y(m);
    rep(i,m-1){
        y[i]=abs(x[i]-x[i+1]);
    }
    sort(y.begin(),y.end());
    ll ans = 0;
    for(int i = 0;i<m-n+1;++i){
        ans += y[i];

    }
    cout<<ans<<endl;

}


Measured memory_bytes: 4032
#define _USE_MATH_DEFINES  // M_PI等のフラグ

#include <iostream>
#include <bitset>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <list>

#define MOD 1000000007
#define COUNTOF(array) (sizeof(array)/sizeof(array[0]))

using namespace std;


void solve(){
    string S;
    cin >> S;

    uint64_t ans = 0;
    int n = S.length()-1;

    for (int i=0; i<(1<<n); i++) {
        bitset<10> bit(i);

        int pre_j = 0;
        for (int j=0; j<n; j++) {
            if (bit.test(j)) {
                ans += stoull(S.substr(pre_j, (j+1-pre_j)));
                pre_j = j+1;
            }
        }
        if (pre_j != S.length()) {
            ans += stoull(S.substr(pre_j, S.length()-pre_j));
        }
    }

    cout << ans << endl;
}

int main(int argc, char const *argv[]){
    solve();
    return 0;
}

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

const int N = 2e5 + 10, mod = 1e9 + 7;


int main() {
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1; 
    //scanf("%d", &tc);
    while(tc--) {
        int x, y, a, b, c; cin >> x >> y >> a >> b >> c;
        vector<int> arr(a);
        for(int &it : arr) scanf("%d", &it);
        vector<int> brr(b);
        for(int &it : brr) scanf("%d", &it);
        vector<int> crr(c);
        for(int &it : crr) scanf("%d", &it);

        multiset<int> res;
        long long ans = 0;
        sort(arr.begin(), arr.end());
        sort(brr.begin(), brr.end());
        int need = (int)arr.size() - x;
        while(arr.size() > need) res.insert(arr.back()), arr.pop_back();
        need = (int)brr.size() - y;
        while(brr.size() > need) res.insert(brr.back()), brr.pop_back();

        sort(crr.rbegin(), crr.rend());

        // for(int x : as) cout << x << ' ';
        // cout << '\n';
        // for(int x : bs) cout << x << ' ';
        // cout << '\n';

        for(int cur : crr) {
            auto it = res.begin();
            if(cur > *it) {
                res.erase(it);
                res.insert(cur);
            }
        }

        for(int it : res) ans += it;

        printf("%lld\n", ans);
    }    
    return 0;
}

Measured memory_bytes: 9856
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,b,c,x,cnt=0;
    cin >> a >> b >>c>>x;
    for(int i =0;i<=a;i++){
        for(int j =0;j<=b;j++){
            for(int l=0;l<=c;l++){
                if(i*500+j*100+l*50==x){
                    cnt++;
                }
            }
        }
    }
    
        cout << cnt;
    
}


Measured memory_bytes: 256
def solve():
    import sys
    from heapq import heappush, heappop
    file_input = sys.stdin
    inf = float('inf')
    
    while True:
        n, m = map(int, file_input.readline().split())
        if n == 0:
            break
        
        s, g = map(int, file_input.readline().split())
        
        adj_list = [[] for i in range(n)]
        for i in range(m):
            x, y, d, c = map(int, file_input.readline().split())
            x -= 1
            y -= 1
            adj_list[x].append((y, d, c))
            adj_list[y].append((x, d, c))
        
        # Dijkstra's algorithm
        s -= 1
        g -= 1
        time_rec = [[[inf] * 31 for j in range(n)] for i in range(n)]
        time_rec[s][s][1] = 0
        
        # pq element: (time, current city, previous city, speed)
        pq = [(0, s, s, 0)]
        
        while pq:
            t, c, p, s = heappop(pq)
            
            if time_rec[p][c][s] < t:
                continue
            
            if c == g and s == 1:
                print(t)
                break
            
            for next_city, d, s_limit in adj_list[c]:
                if next_city == p:
                    continue
                
                if s <= 1:
                    lower_limit = 1
                else:
                    lower_limit = s - 1
                    
                for shifted_s in range(lower_limit, s + 2):
                    if shifted_s > s_limit:
                        continue
                    
                    next_t = t + d / shifted_s
                    
                    if time_rec[c][next_city][shifted_s] <= next_t:
                        continue
                    else:
                        heappush(pq, (next_t, next_city, c, shifted_s))
                        time_rec[c][next_city][shifted_s] = next_t
        else:
            print('unreachable')

solve()


Measured memory_bytes: 7860
#include <bits/stdc++.h>
using namespace std;
int main(){
	string S; cin >> S; 
	int N = S.size(); 
	map<int, int> M; 
	int A[200010] = {}; 
	bool odd[30] = {}; 
	for(int i = 1; i <= N; i++){
		int c = S.at(i-1) - 'a'; 
		if(odd[c]){
			A[i] = A[i-1] - (1 << c); 
			odd[c] = false; 
		}
		else{
			A[i] = A[i-1] + (1 << c); 
			odd[c] = true; 
		}
	}
	M[0] = 1; 
	for(int i = 1; i <= N; i++){
		int tmp = 1145141919;
		if(M[A[i]]) tmp = M[A[i]];  
		for(int j = 0; j < 26; j++){
			if(((A[i] >> j) & 1) && M[A[i] - (1 << j)]){
				tmp = min(tmp, M[A[i] - (1 << j)] + 1); 
			}
			if(!((A[i] >> j) & 1) && M[A[i] + (1 << j)]){
				tmp = min(tmp, M[A[i] + (1 << j)] + 1); 
			}
		}
		M[A[i]] = tmp;
	}
	cout << max(M[A[N]] - 1, 1) << endl; 
}

Measured memory_bytes: 205060
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner scanner = new Scanner(System.in);
        
        int count = 0;
        
        for(int i=0; i<5; i++){
            
            int N = scanner.nextInt();
            
            if(N!=i+1){
                count = i+1;
                break;
            }
            
        }
        System.out.println(count);
        
    }
}


Measured memory_bytes: 35672
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<bits/stdc++.h>
#define ll long long 
#define dd double
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
   
  string s;
  cin>>s;
  if(s=="Sunny"){
  	cout<<"Cloudy"<<endl;
  } 
  
  else if(s=="Cloudy"){
  	cout<<"Rainy"<<endl;
  }
  
  else{
  	cout<<"Sunny"<<endl;
  }
 
  return 0;
}

Measured memory_bytes: 3516
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<ull> ulvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<tuple<ll,ll,ll>> tvec;
typedef vector<string> svec;

int main(){
    string s;
    cin>>s;
    int n=s.size();
    priority_queue<int,vec,greater<int>> que;
    rep(i,n-2){
        int a=0;
        a+=(s[i]-'0')*100;
        a+=(s[i+1]-'0')*10;
        a+=s[i+2]-'0';
        que.push(abs(a-753));
    }
    cout<<que.top();
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main(int argc, char *argv[]) {
	int n,sum;
	cin >> n;
	int res = 0;
	for (int i = 1; i <= n; i += 2){
		sum = 0;
		for(int j = 1; j <= i; j++){
			if(i%j == 0) sum++;
		}
		if (sum == 8) res++;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
stdin =open(0).read().split('\n')
N=int(stdin[0])
A=list(map(int,stdin[1].split()))
from collections import Counter
C=Counter(A)
ans=0
for i in C.values():
    ans+=i*(i-1)//2
for a in A:
    num = C[a]
    print(ans-num*(num-1)//2+(num-1)*(num-2)//2)

Measured memory_bytes: 26180
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL;
  typedef pair<ll,char> PLC;
  typedef pair<char,ll> PCL;

int main(void){
  string S;cin >> S;
  int i,count=0;
  REP(i,S.length()){
    if(S[i] == '+') count++;
    else count--;
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    string s[3];
    rep(i, 0, 3) cin >> s[i];
    rep(i, 0, 3) cout << s[i][0];
    cout << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <stdio.h>

int main()
{
    int n;
    int max = 0;
    scanf("%d",&n);
    int price[10];
    int sum = 0; 
    for(int j=0;j<n;j++){
        scanf("%d",&price[j]);
        if(price[j]>max) {
            sum += max;
            max = price[j];
        }
        else sum+= price[j];
    }
    sum += max/2;
    printf("%d",sum);
    return 0;
}

Measured memory_bytes: 128
function main() {
  var
  i, j, n, m,
  table, line, str;
  for(i = 0; n = parseInt(input[i++], 10); ) {
    table = {};
    for(j = 0; j < n; j++) {
      line = input[i++].split(' ');
      table[line[0]] = line[1];
    }
    m = parseInt(input[i++], 10);
    str = [];
    for(j = 0; j < m; j++, i++) {
      str.push(table[input[i]] || input[i]);
    }
    console.log(str.join(''));
  }
}

var
input = '';

process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
  input += chunk;
});
process.stdin.on('end', function() {
  input = input.split(/\r\n|\r|\n/g);
  main();
});

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

int main(){
    map<int,int> seq;
    int N;
    cin >> N;
    int x;
    while( cin >> x ){
        if( seq.find(x) != seq.end() ) seq[x]++;
        else seq.insert(make_pair(x,1));
    }
    int ans = 0;
    for( pair<int,int> k : seq ){
        ans += k.second;
        if( k.second >= k.first ) ans -= k.first;
    }

    cout << ans << endl;
}

Measured memory_bytes: 4736
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kein Yukiyoshi
 */

#include "bits/stdc++.h"
#define int long long
#define rep(i, n)           for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b)        for (int i = (int)(a); i < (int)(b); i++)
#define FOR(i, a)           for (auto &i : a)
#define ALL(obj)            begin(obj), end(obj)
#define MAX(x)              *max_element(ALL(x))
#define MIN(x)              *min_element(ALL(x))
#define SUM(x)              accumulate(ALL(x), 0LL)
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))

using namespace std;
const int MOD    = (int)(1e9 + 7);
const int INF    = (int)(1e13 + 7);
const double EPS = 1e-14;
const double PI  = acos(-1);

int CEIL(int a, int b) { return (a >= 0 ? (a + (b - 1)) / b : (a - (b - 1)) / b); } //ceil() for int
int mod(int a, int b) { return a >= 0 ? a % b : a - (b * CEIL(a, b)); }             //always return positive num
int bpm(int a, int b) {                                                             //return x^y in order(log(y))
  int res = 1;
  for (a %= MOD; b; a = a * a % MOD, b >>= 1)
    if (b & 1) res = res * a % MOD;
  return res;
}

class CBackAndForth {
public:
  static void solve(istream &cin, ostream &cout) {
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    string ans = "";
    ans += string(ty - sy, 'U') + string(tx - sx, 'R') + string(ty - sy, 'D') + string(tx - sx, 'L') + 'L';
    ans += string(ty - sy + 1, 'U') + string(tx - sx + 1, 'R') + 'D';
    ans += 'R' + string(ty - sy + 1, 'D') + string(tx - sx + 1, 'L') + 'U';
    cout << ans << endl;
  }
};


signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
  CBackAndForth solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}


Measured memory_bytes: 3624
open Batteries
(* 前からst文字を消す *)
let cut st str = String.init (String.length str - st) (fun a -> String.get str (a+st))
(* 後ろからed文字を消す *)
let back_cut ed str = String.init (String.length str - ed) (String.get str)
let n = read_int ()
let s = read_line ()
let l = String.length s / 2
let _ = 
  (if n mod 2 = 1 then "No" else
  if cut l s = back_cut l s then "Yes" else "No") |> print_endline

Measured memory_bytes: 3072
S = list(input())
l = [0] * 5
ind = 0
f = True

for i in range(len(S)):
    if (S[i] == 'A' or S[i] == 'C' or S[i] == 'G' or S[i] == 'T') and f:
        l[ind] += 1
    elif (S[i] == 'A' or S[i] == 'C' or S[i] == 'G' or S[i] == 'T') and f == False:
        l[ind] += 1
    else:
        f = False
        ind += 1
print(max(l))

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll N; cin >> N;
    vector<ll> a(N+2); rep(i, N){cin >> a.at(i + 1);}
    a.at(0) = 0; a.at(N+1) = 0;
    // for (auto v: a){cout << v << endl;}
    ll sum = 0;
    rep(i, N+1){sum += abs(a.at(i + 1) - a.at(i));}
    rep2(i, 1, N+1){
        cout << sum - abs(a.at(i + 1) - a.at(i)) - abs(a.at(i) - a.at(i - 1)) + abs(a.at(i + 1) - a.at(i - 1)) << endl;
    }
}

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


Measured memory_bytes: 2048
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX_N 100000
#define float int
long long float N;
long long float M;
long long float a[3 * MAX_N];

int main() {
    cin >> N;
    for(long long float i=0;i<3*N;i++) {
        scanf("%d", a + i);
    }
    priority_queue<long long float, vector<long long float>, greater<long long float>> q_left;
    priority_queue<long long float> q_right;
    long long float sum_left = 0;
    long long float sum_right = 0;
    for(long long float i=0;i<N;i++) {
        q_left.push(a[i]);
        q_right.push(a[3*N-i-1]);
        sum_left += a[i];
        sum_right += a[3*N-i-1];
    }
    long long float ans = sum_left - sum_right;
    auto dl = vector<long long float>(N+1);
    auto dr = vector<long long float>(N+1);
    dl[0] = sum_left;
    dr[N] = sum_right;
    for(long long float i=0;i<N;i++) {
        q_left.push(a[i+N]);
        sum_left -= q_left.top();
        sum_left += a[i+N];
        q_left.pop();
        dl[i+1] = sum_left;
    }
    for(long long float i=0;i<N;i++) {
        q_right.push(a[2*N-i-1]);
        sum_right -= q_right.top();
        sum_right += a[2*N-i-1];
        q_right.pop();
        dr[N-i-1] = sum_right;
    }
    for(long long float i=0;i<N+1;i++) {
        ans = max(ans, dl[i] - dr[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5996
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9+7;
main(){
    int N,num = 0;
    string s;
    cin >> N >> s;
    for(int i = 0;i < s.length();i++){
        if(s[i] == '(')num++;
        if(s[i] == ')')num--;
        if(num < 0){
            s = '(' + s;
            num++;
            i++;
        }
    }
    s += string(num,')');
    cout << s << endl;
}

Measured memory_bytes: 256
use std::io::{BufRead, BufWriter, Write};

fn main() {
    let stdin = std::io::stdin();
    let stdout = std::io::stdout();
    solve(&mut stdin.lock(), &mut BufWriter::new(stdout.lock()));
}

fn solve<R: BufRead, W: Write>(stdin: &mut R, stdout: &mut BufWriter<W>) {
    let (n, k): (usize, usize) = stdin.gets().split(' ').values();
    let x = stdin.gets().split(' ').take(n).map(|x| x.parse().unwrap())
        .collect::<Vec<i32>>();
    let mut ans = std::i32::MAX;
    for pl in 0..n - k + 1 {
        let pr = pl + k - 1;
        let d = if x[pr] < 0 {
            -x[pl]
        } else if x[pl] < 0 {
            x[pr] - x[pl] + std::cmp::min(-x[pl], x[pr])
        } else {
            x[pr]
        };
        ans = std::cmp::min(ans, d);
    }
    writeln!(stdout, "{}", ans).unwrap();
}

trait Gets { fn gets(&mut self) -> String; }
impl<T: std::io::BufRead> Gets for T {
    fn gets(&mut self) -> String { self.lines().next().unwrap().unwrap() } }

trait Values<T> { fn values(&mut self) -> T; }
impl<'a, I, T1, T2> Values<(T1, T2)> for I
    where I: Iterator<Item=&'a str>,
          T1: std::str::FromStr, T1::Err: std::fmt::Debug,
          T2: std::str::FromStr, T2::Err: std::fmt::Debug {
    fn values(&mut self) -> (T1, T2) {
        (self.next().unwrap().parse().unwrap(),
         self.next().unwrap().parse().unwrap())
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e12;

// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

// 入力
// 入力
int H, W, N;
int sx, sy, gx, gy; 
vector<vector<char>> field;
vector<vector<int>> dist;
queue<pair<int, int>> que;

int main() {

    string S, T;
    int count = 0;
    bool flag = false;
    int i= 0, pos;

    cin >> S; cin >> T;

    for(i= 0; i + T.length() <= S.length(); i++){
        count = 0;
        for(int j = 0; j < T.length(); j++){
            if(S[i+j] == T[j] || S[i+j] == '?'){
               // cout << S[i+j] << " " << T[j] << endl;
                count++;
            }
            else break;
        }
        if(count == T.length()){
            pos = i;
            flag = true;
        }
    }

    if(flag == true){
        S.replace(pos, T.length(), T);
        for(int i= 0; i <= S.length(); i++){
            if(S[i] == '?') S[i] = 'a';        
        }
    } else {
        S = "UNRESTORABLE";
    }

    cout << S << endl;

}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define pb push_back
#define mp make_pair
 #define mod 1000000007
 const int N=100005;
 const int inf=1e18;
int pow(int a,int b){
    int res=1;
    while(b>0){
        if(b&1){
        	res=res*a;
		}
        a=a*a;
        b>>=1;
    }
    return res;
}
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	int n;
	cin>>n;
	int a[n];
	for(int x=0;x<n;x++){
		cin>>a[x];
	}
	int c=0;
	for(int x=n-1;x>0;x--){
		if(a[x]<a[x-1]){
			if(a[x-1]-a[x]==1){
				a[x-1]--;
			}else{
				c++;
				break;
			}
		}
	}
	if(c==0){
		cout<<"Yes";
	}else{
		cout<<"No";
	}
	
	








	
return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 5001;
int arr[mxN];
int dsu[mxN];
int sz[mxN];
int cnt[mxN];
ll dp[mxN];
ll fact[mxN];
int n;
int find(int a) {
    return a==dsu[a] ? a : (dsu[a] = find(dsu[a]));
}
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if(a==b)return;
    dsu[a] = b;
    sz[b]+=sz[a];
}
int main()
{   
    //freopen("exercise.in", "r", stdin);
    //freopen("exercise.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    int k= 0;
    fact[0] = 1;
    owo(i, 1, mxN) {
        fact[i] = (fact[i-1]*i)%MOD;
    }
    owo(i, 0, n) {
        sz[i] = 1;
        dsu[i] = i;
    }
    owo(i, 0, n) {
        cin>>arr[i];
        if(arr[i]!=-1) {
            arr[i]--;
            merge(i, arr[i]);
        }else k++;
    }
    owo(i, 0, n) {
        if(arr[i]!=-1)cnt[find(i)]++;
    }
    ll ans= 0;
    vector<ll> cyc;
    owo(i, 0, n) {
        if(find(i)==i&&cnt[i]!=sz[i]) {
            cyc.senpai(sz[i]);
        }else if(find(i)==i){
            ans = (ans + binpow(n-1, k))%MOD;
        }
    }
    dp[0] = 1;
    for(ll p: cyc) {
        uwu(i, cyc.size(), 0) {
            dp[i+1] = (dp[i+1] + (dp[i]*p)%MOD)%MOD;
        }
    }
    owo(i, 2, cyc.size()+1) {
        ans = (ans + (((binpow(n-1, cyc.size()-i)*dp[i])%MOD)*fact[i-1])%MOD)%MOD;
    }
    for(ll p: cyc) {
        ans = (ans + (binpow(n-1, cyc.size()-1)*1LL*(p-1))%MOD);
    }
    ans = (binpow(n-1, k)*1LL*n- ans)%MOD+MOD;
    ans%=MOD;
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 3848
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<functional>
#include<map>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,P> PP;
int r;
ll INF;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int w[2],h[2],x[2],y[2];
ll dp[2][500001];
ll fie[2][501][501];
bool used[2][501][501];

void dijk(int f){
	priority_queue<PP,vector<PP>,greater<PP> > que;
	que.push(PP(fie[f][x[f]][y[f]],P(x[f],y[f])));
	int cnt=1;
	while(que.size()){
		PP p=que.top();
		que.pop();
		ll cost=p.first;
		int px=p.second.first;
		int py=p.second.second;
		if(used[f][px][py])continue;
		used[f][px][py]=true;
		dp[f][cnt]=max(cost,dp[f][cnt-1]);
		cnt++;
		for(int i=0;i<4;i++){
			int nx=px+dx[i];
			int ny=py+dy[i];
			if(nx>=0 && nx<w[f] && ny>=0 && ny<h[f]){
				if(!used[f][nx][ny]){
					que.push(PP(fie[f][nx][ny],P(nx,ny)));
				}
			}
		}
	}
}

int main(void){
	while(1){
		INF=0;
		memset(dp,0,sizeof(dp));
		memset(fie,0,sizeof(fie));
		memset(used,false,sizeof(used));
		scanf("%d",&r);
		if(r==0)break;
		scanf("%d%d%d%d",&w[0],&h[0],&x[0],&y[0]);
		x[0]--,y[0]--;
		for(int i=0;i<h[0];i++){
			for(int j=0;j<w[0];j++){
				scanf("%lld",&fie[0][j][i]);
				INF+=fie[0][j][i];
			}
		}
		scanf("%d%d%d%d",&w[1],&h[1],&x[1],&y[1]);
		x[1]--,y[1]--;
		for(int i=0;i<h[1];i++){
			for(int j=0;j<w[1];j++){
				scanf("%lld",&fie[1][j][i]);
				INF+=fie[1][j][i];
			}
		}
		dijk(0);
		dijk(1);
		ll res=INF;
		for(int i=0;i<=r;i++){
			if(w[0]*h[0]<i)continue;
			if(w[1]*h[1]<r-i)continue;
			res=min(res,dp[0][i]+dp[1][r-i]);
		}
		printf("%d\n",res);
	}
	return 0;
}

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

int main() {
  int64_t n, k;
  std::cin >> n >> k;
  std::vector<std::vector<int64_t>>
  b(2 * k, std::vector<int64_t>(2 * k, 0)),
  w(2 * k, std::vector<int64_t>(2 * k, 0));

  for (int64_t i = 0; i < n; i++) {
    int64_t x, y;
    char c;
    std::cin >> x >> y >> c;

    if (c == 'B') {
      b[x % (2 * k)][y % (2 * k)]++;
    } else {
      w[x % (2 * k)][y % (2 * k)]++;
    }
  }

  for (int i = 0; i < 2 * k; i++) {
    for (int j = 1; j < 2 * k; j++) {
      b[i][j] += b[i][j - 1];
      w[i][j] += w[i][j - 1];
    }
  }

  for (int i = 0; i < 2 * k; i++) {
    for (int j = 1; j < 2 * k; j++) {
      b[j][i] += b[j - 1][i];
      w[j][i] += w[j - 1][i];
    }
  }

  int64_t count = 0;

  auto calc_b = [&](auto x1, auto y1, auto x2, auto y2) -> int64_t {
    if (x2 < 0 || y2 < 0) {
      return 0;
    }
    if (2 * k - 1 <= x1 || 2 * k - 1 <= y1) {
      return 0;
    }
    x2 = std::min<int64_t>(x2, 2 * k - 1);
    y2 = std::min<int64_t>(y2, 2 * k - 1);
    auto val = b[x2][y2];
    if (0 <= x1) {
      val -= b[x1][y2];
    }
    if (0 <= y1) {
      val -= b[x2][y1];
    }
    if (0 <= x1 && 0 <= y1) {
      val += b[x1][y1];
    }
    return val;
  };
  auto calc_w = [&](auto x1, auto y1, auto x2, auto y2) -> int64_t {
    if (x2 < 0 || y2 < 0) {
      return 0;
    }
    if (2 * k - 1 <= x1 || 2 * k - 1 <= y1) {
      return 0;
    }
    x2 = std::min<int64_t>(x2, 2 * k - 1);
    y2 = std::min<int64_t>(y2, 2 * k - 1);
    auto val = w[x2][y2];
    if (0 <= x1) {
      val -= w[x1][y2];
    }
    if (0 <= y1) {
      val -= w[x2][y1];
    }
    if (0 <= x1 && 0 <= y1) {
      val += w[x1][y1];
    }
    return val;
  };

  for (int i = 0; i < 2 * k; i++) {
    for (int j = 0; j < 2 * k; j++) {
      if (k <= i && k <= j) {
        continue;
      }
      auto b_c = calc_b(i - 1, j - 1, i + k - 1, j + k - 1);
      auto w_c = calc_w(i - 1, j - 1, i + k - 1, j + k - 1);
      b_c += calc_b(i - 1 - k, j - 1 - k, i - 1, j - 1);
      w_c += calc_w(i - 1 - k, j - 1 - k, i - 1, j - 1);
      b_c += calc_b(i - 1 - k, j + k - 1, i - 1, j + 2 * k - 1);
      w_c += calc_w(i - 1 - k, j + k - 1, i - 1, j + 2 * k - 1);

      b_c += calc_b(i + k - 1, j - 1 - k, i + 2 * k - 1, j - 1);
      w_c += calc_w(i + k - 1, j - 1 - k, i + 2 * k - 1, j - 1);
      b_c += calc_b(i + k - 1, j + k - 1, i + 2 * k - 1, j + 2 * k - 1);
      w_c += calc_w(i + k - 1, j + k - 1, i + 2 * k - 1, j + 2 * k - 1);

      b_c += calc_b(i - 2 * k - 1, j - 1, i - k - 1, j + k - 1);
      w_c += calc_w(i - 2 * k - 1, j - 1, i - k - 1, j + k - 1);

      b_c += calc_b(i - 1, j - 2 * k - 1, i + k - 1, j - k - 1);
      w_c += calc_w(i - 1, j - 2 * k - 1, i + k - 1, j - k - 1);
      count = std::max(count, b_c + w[2 * k - 1][2 * k - 1] - w_c);
    }
  }

  std::cout << count << std::endl;
  return 0;
}

Measured memory_bytes: 64896
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <unordered_map>
#include <math.h>
#include <cctype>
using namespace std;
#define _USE_MATH_DEFINES

int a[100];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	for (int ii = 0; ii < N; ii++) {
		cout << a[ii];
		if (ii != N - 1)
			cout << " ";
		else
			cout << endl;
	}
	for (int i = 1; i < N; i++) {
		int key = a[i];
		int j = i - 1;
		while (j >= 0 && a[j]>key) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = key;
		for (int ii = 0; ii < N; ii++) {
			cout << a[ii];
			if (ii != N - 1)
				cout << " ";
			else
				cout << endl;
		}
	}
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define ll long long
#define endl "\n"
#define vi vector<int>
#define vl vector<ll>
#define all(v) (v).begin(),(v).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
using namespace std;
const ll N=15;
int a[N],n,m,q,res;
int l[55],r[55],c[55],d[55];
void dfs(int p, int x){
    if(p==n){
        int ans=0;
        for(int i=0;i<q;i++){
            if(a[r[i]-1]-a[l[i]-1]==c[i])
                ans+=d[i];
        }
        res=max(res,ans);
        return;
    }
    for(int i=x;i<=m;i++){
        a[p]=i;
        dfs(p+1,i);
    }
}
void solve(){
    cin>>n>>m>>q;
    for(int i=0;i<q;i++)
        cin>>l[i]>>r[i]>>c[i]>>d[i];
    res=0;
    dfs(0,1);
    cout<<res<<endl;
}

// don't forget to check for overflows in final answers
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll t,p;
    t=1;
    //cin>>t;
    for(p=1;p<=t;p++){
        solve();
    }
}


Measured memory_bytes: 3628
#include <iostream>

using namespace std;

#define int_64 long long

const int N = 2e5 + 10;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);    
  int h, w, k;
  cin >> h >> w >> k;
  char s[h][w];
  for (int i = 0; i < h; ++i) {
    cin >> s[i];
  }
  int ans = 0;
  for (int i = 0; i < (1 << h); ++i) {
    for (int j = 0; j < (1 << w); ++j) {
      int cur = 0;
      for (int l = 0; l < h; ++l) {
        for (int m = 0; m < w; ++m) {
          if (i & (1 << l) || j & (1 << m)) {
            continue;
          }
          cur += s[l][m] == '#';
        }
      }
      ans += cur == k;
    }
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    // Your code here!
    ll t,x;
    cin>>t>>x;
    cout<<setprecision(10)<<(1.*t)/(1.*x)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//(a+b-1)/b

int f(int a){
	if(a==1)return 300000;
	else if(a==2) return 200000;
	else if(a==3) return 100000;
	return 0;
}
signed main(){
	int a,b; cin>>a>>b;
	int ans=0;
	if(a==1 && b==1)ans+=400000;
	ans+=f(a);
	ans+=f(b);
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3616
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

signed main(){
	cout<<fixed<<setprecision(12);
	
	long double pi = acos(-1);
	
	long double A, B, H, M;
	long double ans;
	long double ay, ax;
	long double by, bx;
	
	cin>>A>>B>>H>>M;
	
	
	
	// ax = cos(pi/2 - (2 * pi * H)/12.0) * A;
	// ay = sin(pi/2 - (2 * pi * H)/12.0) * A;
	
	ax = cos(pi/2 - (2 * pi * (H * 60 + M))/720.0) * A;
	ay = sin(pi/2 - (2 * pi * (H * 60 + M))/720.0) * A;
	
	bx = cos(pi/2 - (2 * pi * M)/60.0) * B;
	by = sin(pi/2 - (2 * pi * M)/60.0) * B;
	
	// cout<<ax<<" "<<ay<<" "<<sqrt(ax*ax + ay*ay)<<endl;
	// cout<<bx<<" "<<by<<" "<<sqrt(bx * bx + by*by)<<endl;
	
	
	ans = sqrt((ax - bx) * (ax - bx) + (by - ay) * (by - ay));
	
	cout<<ans<<endl;
	
	return 0;
}

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

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

  int N, M;
  cin >> N >> M;
  cout << (N-1)*(M-1) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fo(i, n) for (i = 0; i < n; i++)
#define ll long long
#define pb push_back
#define mp make_pair
// #define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int mpow(int base, int exp);
void ipgraph(int n, int m);
void dfs(int u, int par);
const int mod = 1'000'000'007;
const int N = 3e5, M = N;

void solve()
{
    ll i, j, n, m;
    cin >> n;
    ll dp[n];
    ll a[n];
    ll cost1 = 0, cost2 = 0;
    fo(i, n)
    {
        cin >> a[i];
    }

    dp[0] = 0;
    dp[1] = abs(a[1] - a[0]);

    for (i = 2; i < n; i++)
    {
        cost1 = dp[i - 1] + abs(a[i] - a[i - 1]);
        cost2 = dp[i - 2] + abs(a[i] - a[i - 2]);
        dp[i] = min(cost1, cost2);
    }

    cout << dp[n - 1];
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

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

    return 0;
}


Measured memory_bytes: 5180
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
int a[111], v[111];
ll s[100010];
int main(){
    int n, w;
    while(cin>>n>>w){
        ll ans=0;
        for(int i=0; i<n; ++i){
            scanf("%d%d",a+i, v+i);
        }
        memset(s, -1, sizeof s);
        s[0]=0;
        for(int i=0; i<n; ++i){
            for(int j=w; j>=a[i]; --j){
                if(s[j-a[i]]!=-1)
                    s[j]=max(s[j], s[j-a[i]]+v[i]);
                ans=max(ans, s[j]);
            }
        }
        cout<<ans<<endl;
    }
  return 0;
}




Measured memory_bytes: 1024
N = int(input())
H = list(map(int, input().split()))

#dp[足場i]=足場iにたどり着く最小コスト
dp = [10**7 for _ in range(N+10)]

dp[0] = 0
dp[1] = abs(H[0]-H[1])
for i in range(2,N):
    dp[i] = min(dp[i-1]+abs(H[i]-H[i-1]), dp[i-2]+abs(H[i]-H[i-2]))

print(dp[N-1])

Measured memory_bytes: 13924
#include<bits/stdc++.h>
#define N_MAX 100
#define INF (1e9)
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> P1;
typedef pair<int,P> P2;
int a,b,c,h,r,s,t,p,l,d,k,ans;
int N,M,H,K,dp[300][(1<<8)];
vector<P1> v[N_MAX];
P L[300];

void dijkstra(int S,int C){
  int d[25][N_MAX];
  priority_queue<P2,vector<P2>,greater<P2> > q;
  for(int i=0;i<=H;i++)
    for(int j=0;j<N;j++)d[i][j]=INF;
  d[0][s-1]=0;
  q.push(P2(0,P(0,s-1)));
  while(!q.empty()){
    P2 A=q.top(); q.pop();
    int cost=A.first;
    int tim=A.second.first;
    int x=A.second.second;
    if(d[tim][x]<cost)continue;
    for(int i=0;i<v[x].size();i++){
      int nx=v[x][i].first.first;
      int pc=v[x][i].first.second;
      int ph=v[x][i].second.first;
      int R=v[x][i].second.second;
      if(tim+ph<=H){
	if(!(S&(1<<R))&&d[tim+ph][nx]>cost+pc){
	  d[tim+ph][nx]=cost+pc;
	  q.push(P2(cost+pc,P(tim+ph,nx)));
	}
	if((S&(1<<R))&&d[tim+ph][nx]>cost){
	  d[tim+ph][nx]=cost;
	  q.push(P2(cost,P(tim+ph,nx)));
	}
      }
    }
  }
  int mind=INF;
  for(int i=0;i<=H;i++)mind=min(mind,C+d[i][t-1]);
  ans=min(ans,mind);
}

int main(){
  while(1){
    cin>>N>>M>>H>>K;
    if(!N&&!M&&!H&&!K)break;
    for(int i=0;i<M;i++){
      cin>>a>>b>>c>>h>>r;
      v[a-1].push_back(P1(P(b-1,c),P(h,r-1)));
      v[b-1].push_back(P1(P(a-1,c),P(h,r-1)));
    }
    cin>>s>>t;
    cin>>p;
    for(int i=0;i<=p;i++)
      for(int j=0;j<(1<<K);j++)dp[i][j]=INF;
    for(int i=0;i<p;i++){
      cin>>l>>d;
      L[i]=P(d,0);
      for(int j=0;j<l;j++)cin>>k,L[i].second|=(1<<(k-1));
      dp[i][L[i].second]=d;
    }
    for(int i=0;i<p;i++){
      for(int j=0;j<(1<<K);j++){
	if(dp[i][j]==INF)continue;
	dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
	dp[i+1][j|L[i].second]=min(dp[i+1][j|L[i].second],dp[i][j]+L[i].first);
      }
    }
    ans=INF;
    dijkstra(0,0);
    for(int i=0;i<(1<<K);i++){
      if(dp[p][i]==INF)continue;
      dijkstra(i,dp[p][i]);
    }
    if(ans!=INF)cout<<ans<<endl;
    else cout<<-1<<endl;
    for(int i=0;i<N;i++)v[i].clear();
  }
  return 0;
}

Measured memory_bytes: 1640
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

long long a, b;

int main() { 

  cin >> a >> b;

  long long ans = 0;
  if (a & 1) {
    ans ^= a;
    a++;
  }
  if (b >= a && b % 2 == 0) {
    ans ^= b;
    b--;
  }

  if (b >= a) {
    if (((b - a + 1) / 2) & 1) {
      ans ^= 1;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
//by Top1
#include <bits/stdc++.h>
          
#define f first
#define s second
#define int long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define pll pair <long, long>
#define mp make_pair
#define pb push_back
#define pf push_front
#define pp pop_back
#define cerr cout
#define rev reverse
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define forn(i, a, b) for (int i = a; i <= b; i++)
#define boost ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);
#define nxtp next_permutation
#define pvtp prev_permutation
#define KZ return 
#define x1 x21212121
#define y1 y21212121
#define sqr(x) x * x 
      
const int inf = (1e9) + 1;
const int mod = 479001599;
const int maxn = 3e6 + 111;
        
using namespace std;          

int a[maxn], n, x;

void solve(){
	cin >> n;

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

	for (int i = 1; i <= n; i++)
		cout << a[i] << endl;
}                              
      
main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

    boost;
    
    int q = 1;
 
    //cin >> q;
    
    while (q--){
        solve();
    }
}

Measured memory_bytes: 5144
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind
#define rt (a); return (a); 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 1000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
llint gcd(llint a, llint b) {
	if (b > a)swap(a, b);
	if (a % b == 0)return b;
	return gcd(b, a % b);
}
llint Tow(int n) {//2のn乗
	if (n == 0)return 1;
	llint x = Tow(n / 2);
	x %= mod;
	x *= x;
	x %= mod;
	if (n % 2 == 1)x *= 2;
	x %= mod;
	return x;
}
int main() {
	int n;
	cin >> n;
	hei(int) a(n);
	int zero = 0;
	hei(int) A;
	if (n%2 == 1) {
		rep(i, 0, n) {
			cin >> a[i];
			if (a[i] == 0)zero++;
			else A.push_back(a[i]);
		}
		if (zero!=1) {
		S:
			cout << 0 << endl;
			return 0;
		}
		sort(A);
		A.push_back(0);
		int x = 1;
		rep(i, 0, A.size()-1) {
			if (A[i] == A[i + 1])x++;
			else {
				if (x != 2)goto S;
				x = 1;
			}
		}
		llint ans = Tow(n / 2);
		cout << ans << endl;
	}
	else {
		rep(i, 0, n) {
			cin >> a[i];
			if (a[i] == 0) {
				cout << 0 << endl;
				return 0;
			}
			A.push_back(a[i]);
		}
		sort(A);
		A.push_back(0);
		int x = 1;
		rep(i, 0, A.size() - 1) {
			if (A[i] == A[i + 1])x++;
			else {
				if (x != 2)goto S;
				x = 1;
			}
		}
		llint ans = Tow(n / 2);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1276
A,B,C,Y,X = map(int, input().split())
m1 = A * Y + B * X
m2 = C * 2 * min(X,Y) + A * max(Y-X, 0) + B * max(X-Y,0)
m3 = C * 2 * max(X,Y)
print(min(m1,m2,m3))

Measured memory_bytes: 3060