akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <queue>
#include <tuple>

constexpr size_t m1 = -1;
constexpr size_t di[] = {m1, m1, m1, 0, 0, 1, 1, 1};
constexpr size_t dj[] = {m1, 0, 1, m1, 1, m1, 0, 1};

int main() {
  size_t h, w;
  intmax_t a, b;
  scanf("%zu %zu %jd %jd", &h, &w, &a, &b);

  std::vector<std::string> c(h);
  size_t si, sj, gi, gj;
  for (size_t i = 0; i < h; ++i) {
    char buf[1024];
    scanf("%s", buf);
    c[i] = buf;
    for (size_t j = 0; j < w; ++j) {
      if (c[i][j] == 's') {
        si = i;
        sj = j;
      } else if (c[i][j] == 'g') {
        gi = i;
        gj = j;
      }
    }
  }

  std::vector<intmax_t> cost{a+a, a, a+a, a, a, a+a, a, a+a};

  intmax_t INF = 2e12;
  std::vector<std::vector<intmax_t>> dp(h, std::vector<intmax_t>(w, INF));
  std::queue<std::pair<size_t, size_t>> q;
  q.emplace(si, sj);
  dp[si][sj] = 0;
  while (!q.empty()) {
    size_t i, j;
    std::tie(i, j) = q.front();
    q.pop();

    bool bomb = (c[i][j] == '*');
    for (int k = 0; k < 8; ++k) {
      size_t ni = i + di[k];
      size_t nj = j + dj[k];
      if (!(ni < h && nj < w)) continue;
      if (c[ni][nj] == '*') bomb = true;
    }

    for (int k = 0; k < 8; ++k) {
      size_t ni = i + di[k];
      size_t nj = j + dj[k];
      if (!(ni < h && nj < w)) continue;

      intmax_t ncost = cost[k];
      // bool kotatsu = (c[ni][nj] == '#' || c[i][nj] == '#' || c[ni][j] == '#');
      bool kotatsu = (c[ni][nj] == '#');
      if (i != ni && j != nj)
        kotatsu |= (c[i][nj] == '#' || c[ni][j] == '#');

      if (kotatsu) {
        if (bomb) continue;
        ncost += b;
      }
      if (dp[ni][nj] > dp[i][j] + ncost) {
        dp[ni][nj] = dp[i][j] + ncost;
        q.emplace(ni, nj);
      }
    }
  }

  // for (size_t i = 0; i < h; ++i)
  //   for (size_t j = 0; j < w; ++j)
  //     fprintf(stderr, "%jd%c", dp[i][j], j+1<w? ' ':'\n');

  if (dp[gi][gj] == INF) return puts("INF"), 0;
  printf("%jd\n", dp[gi][gj]);
}



Measured memory_bytes: 11444
#include<stdio.h>

int main()

{
    int a , b ;

    scanf("%d", &a) ;

    b=a%10 ;

    if(b==2||b==4||b==5||b==7||b==9)
    {
        printf("hon\n") ;
    }
    else if(b==0||b==1||b==6||b==8)
    {
        printf("pon\n") ;
    }
    else if(b==3)
    {
        printf("bon\n") ;
    }

    return 0;
}


Measured memory_bytes: 1644
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner std = new Scanner(System.in);
        String text = std.next();
        String first = text.substring(0, 2);
        String last = text.substring(2);
        Integer firstValue = Integer.parseInt(first);
        Integer lastValue = Integer.parseInt(last);

        String format;
        if (availableMonth(firstValue) && availableMonth(lastValue)) {
            format = "AMBIGUOUS";
        } else if (availableMonth(firstValue)) {
            format = "MMYY";
        } else if (availableMonth(lastValue)) {
            format = "YYMM";
        } else {
            format = "NA";
        }

        System.out.println(format);
    }

    static boolean availableMonth(int val) {
        return val >= 1 && val <= 12;
    }
}


Measured memory_bytes: 21460
n = int(input())
s = input()
#最初の二人だけ全探索
#x -> 狼
#o -> 羊
def check(li):
    for i in range(1,n-1):
        if li[i] == 'S':
            if li[i-1] == 'S':
                if s[i] == 'o':
                    li += ['S']
                else:
                    li += ['W']
            else:
                if s[i] == 'o':
                    li += ['W']
                else:
                    li += ['S']
        else:
            if li[i-1] == 'S':
                if s[i] == 'o':
                    li += ['W']
                else:
                    li += ['S']
            else:
                if s[i] == 'o':
                    li += ['S']
                else:
                    li += ['W']
    if li[-1] == 'S':
        if s[-1] == 'o':
            if li[-2] != li[0]:
                return False
        else:
            if li[-2] == li[0]:
                return False
    else:
        if s[-1] == 'o':
            if li[-2] == li[0]:
                return False
        else:
            if li[-2] != li[0]:
                return False

    if li[0] == 'S':
        if s[0] == 'o':
            if li[-1] != li[1]:
                return False
        else:
            if li[-1] == li[1]:
                return False
    else:
        if s[0] == 'o':
            if li[-1] == li[1]:
                return False
        else:
            if li[-1] != li[1]:
                return False
    return li
for i in range(2):
    for j in range(2):
        s1 = 'S' if i == 1 else 'W'
        s2 = 'S' if j == 1 else 'W'
        k = check([s1,s2])
        if k:
            print("".join(k))
            exit()
print(-1)

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

const int dh[4] = {1, 0, -1, 0};
const int dw[4] = {0, 1, 0, -1};

using Graph = vector<string>;
queue<pair<int, int>> suspended;
vector<vector<int>> dist; // dist[i][j]: 位置(sx, sy)から位置(i, j)までの最小手数

int main() {
  int H, W; cin >> H >> W;
  Graph G(H);
  for (int i = 0; i < H; i++) cin >> G[i];
  dist.resize(H);
  for (int i = 0; i < H; i++) {
    dist[i].resize(W);
    dist[i].assign(W, -1);
  }

  dist[0][0] = 0;
  suspended.push(make_pair(0, 0));
  while (!suspended.empty()) {
    int h, w;
    tie(h, w) = suspended.front(); suspended.pop();
    for (int dir = 0; dir < 4; dir++) {
      int nh = h + dh[dir];
      int nw = w + dw[dir];
      if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
      if (dist[nh][nw] != -1) continue;
      if (G[nh][nw] == '#') continue;
      dist[nh][nw] = dist[h][w] + 1;
      suspended.push(make_pair(nh, nw));
    }
  }
  int white = 0;
  int ans = 0;
  for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
          if (G[i][j] == '.') white++;
      }
  }
  if (dist[H-1][W-1] == -1) cout << -1 << endl;
  else cout << white - dist[H-1][W-1] - 1 << endl;
  return 0;
}

Measured memory_bytes: 256
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=10+10;
const int a[11]={0,1,2,4,7,12,20,29,38,53,73};

int n,tot,vis[N]; ll M,G[N][N];

void dfs(int u,int d,ll l) {
	if (d>tot) { M=max(M,l); return; }
	for (int i=1;i<=tot;++i)
		if (!vis[i]) vis[i]=1,dfs(i,d+1,l+G[u][i]),vis[i]=0;
}

int main() {
	n=read();
	for (int i=2;i<=n;++i) {
		for (int j=1;j<i;++j) G[i][j]=G[j][i]=(M+1)*a[j];
		tot=i,dfs(0,1,0);
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			printf("%lld%c",G[i][j]," \n"[j==n]);
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        // 入力
        long[] nm = Console.ReadLine().Split().Select(long.Parse).ToArray();
        var n = nm[0];
        var m = nm[1];

        long ans = 0;
        if (n < m)
        {
            long tmp = (m - (n* 2)) / 4;
            ans = n + tmp;
        }
        else
        {
            long tmp = m/2;
            ans = tmp;
        }

        Console.WriteLine(ans);
    }
}


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

int main(){
    int i, t;
    
    for(i = 1; i <= 9; i++){
        for(t = 1; t <= 9; t++){
            cout << i << "x" << t << "=" << i * t << endl;
        }
    }
    
    return 0;
    
}

Measured memory_bytes: 2992
#include<iostream>
    #include <vector>

    using namespace std;
    int main()
    {
        // 整数の入力
        int N, K;
        cin >> N >> K;
        string people;
        cin >> people;
        int unHappyPlace = 0;
        char prevPeople = people.at(0);
        for (int i = 1; i < N; i++){
            char currentPeople = people.at(i);
            if (prevPeople == currentPeople){
                continue;
            }else{
                unHappyPlace++;
                prevPeople = currentPeople;
            }
        }
        int remainUnHappyPoint = max(unHappyPlace - (K * 2), 0);
        cout << (N - 1) - remainUnHappyPoint;
        return 0;
    }

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

int main() {
  int N,K;
  cin >> N >> K;
  vector<int> H(N);
  for(int i=0;i<N;i++) cin >> H[i];
  sort(H.begin(),H.end());
  
  long long ans=0;
  for(int i=0;i<N-K;i++){
    ans += H[i];
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdint.h>
#include<tgmath.h>
#include<stdbool.h>
#include<sys/queue.h>
#include<time.h>
#define ll long long
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))

ll a, b, x = 0, y = 0;
int main(){
    scanf("%lld%lld", &a, &b);
    for(ll i = a/4*4; i<a; i++)x ^= i;
    for(ll i = b/4*4; i<=b; i++)y ^= i;
    printf("%lld\n", x ^ y);
	return 0;
}

Measured memory_bytes: 1700
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		StringTokenizer st;
		int n, h0, h1, h2, g = 0;
		int[] growth = new int[4];

		while (!(line = br.readLine()).equals("0")) {

			n = Integer.parseInt(line);

			line = br.readLine();
			st = new StringTokenizer(line);

			h1 = Integer.parseInt(st.nextToken());
			for (int i = 0; i < 4; i++) {
				h2 = Integer.parseInt(st.nextToken());
				growth[i] = h2 - h1;
				h1 = h2;
			}
			Arrays.sort(growth);
			for (int i = 0; i < 3; i++) {
				if (growth[i] == growth[i + 1])
					g = growth[i];
			}

			st = new StringTokenizer(line);
			h1 = Integer.parseInt(st.nextToken());
			for (int i = 0; i < n; i++) {
				h2 = Integer.parseInt(st.nextToken());
				if (h2 - h1 != g) {
					if (i == n - 1) {
						System.out.println(h2);
						break;
					}
					h0 = h1;
					h1 = h2;
					h2 = Integer.parseInt(st.nextToken());
					if (h2 - h1 != g) {
						System.out.println(h1);
						break;
					} else {
						System.out.println(h0);
						break;
					}
				} else {
					h1 = h2;
				}
			}
			//
		}
	}
}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pll> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-9;


int M, N, S, T;
int d[2][100][100]; // ??????, ???????¨??????¨

/////////////////////////////////
int dx[2][6] = { {0,1,0,-1,-1,-1}, {1,1,1,0,-1,0} };
int dy[6] = {-1,0,1,1,0,-1};

void solve(int y, int x) {
	queue<pii> que;
	fill(d[1][0], d[2][0], INF);
	
	d[1][y][x] = 0;
	que.push(pii(y, x));
	
	while (!que.empty()) {
		pii now = que.front(); que.pop();
		
		int y = now.fi, x = now.se;
		int c = d[1][y][x];
		
		REP(i, 6) {
			int xx = x + dx[y & 1][i], yy = y + dy[i];
			if (!(xx >= 0 && xx < M && yy >= 0 && yy < N)) continue;
			if (d[1][yy][xx] <= c + 1) continue;
			d[1][yy][xx] = c + 1;
			que.push(pii(yy, xx));
		}
		
	}
}

int main() {

	while (cin >> M >> N, M || N) {
		
		fill(d[0][0], d[2][0], INF);
		
		cin >> S;
		REP(i, S) {
			int x, y; scanf("%d %d", &x, &y);
			solve(y - 1, x - 1);
			REP(j, N) REP(k, M) chmin(d[0][j][k], d[1][j][k]);
		}
		
		int ans = 0;
		
		cin >> T;
		REP(i, T) {
			int x, y; scanf("%d %d", &x, &y);
			solve(y - 1, x - 1);
			
			int cnt = 0;
			REP(j, N) REP(k, M) if (d[0][j][k] > d[1][j][k]) cnt++;
			chmax(ans, cnt);
		}
		
		cout << ans << endl;
		
	}
	return 0;
}

Measured memory_bytes: 3256
#include<stdio.h>

int main(void){
	
	int i=0,j=0;
	char str[20],gyg[20];
	
	scanf("%s",str);
	
	while('\0'!=str[i]){
		i++;
	}
	
	while(i>=0){
		gyg[j]=str[i];
		j++;
		i--;
	}
	
	for(i=0;i<j-1;i++){
		printf("%c",gyg[i+1]);
	}
	
	printf("\n");
	
	return 0;

}

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

namespace abc144_d
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();
            var s = Console.ReadLine();
            var r = 1;
            for (int i = s.Length-1; i > 0; i--)
            {
                if (s[i] != s[i - 1])
                {
                    r++;
                }
            }
            Console.WriteLine(r);
        }
    }
}


Measured memory_bytes: 11232
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    // ちょうどK回、余りから候補を3つ出す、その後その値がありえるか判定
    ll X, K, D;
    cin >> X >> K >> D;
    ll ans = X % D;
    ll time = abs(X - ans) / D;
    if ((time^K) & 1) {
        ans -= D;
        if (abs(ans + 2 * D) < abs(ans)) ans = ans + 2 * D;
    } else {
        if (abs(ans - 2 * D) < abs(ans)) ans = ans - 2 * D;
        if (abs(ans + 2 * D) < abs(ans)) ans = ans + 2 * D;
    }
    if (log10(K) + log10(D) <= 15) ans = min(ans, X + K*D);
    if (log10(K) + log10(D) <= 15) ans = max(ans, X - K*D);
    ans = abs(ans);
    cout << ans << '\n';
    return 0;
}

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

int main(){
  bool flag = true;
  int N;
  cin >> N;
  int x[N], y[N];
  ll h[N];
  rep(i, N){
    cin >> x[i] >> y[i] >> h[i];
  }
  int target = 0;
  rep(i, N){
    if (h[i] >= 1) {
      target = i;
      break;
    }
  }
  for (int i = 100; i >= 0; i--) {
    for (int j = 100; j >= 0; j--) {
      ll H = h[target] + abs(x[target]-i) + abs(y[target]-j);
      rep(k, N){
        ll a = 0;
        ll tyo = max(H - abs(x[k]-i) - abs(y[k]-j), a);
        if (tyo != h[k]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        if (H != 0) {
          cout << i << " " << j << " " << H << endl;
          exit(0);
        }
      }else{
        flag = true;
      }
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define getbit(n,i) (((n)&(1LL<<(i)))!=0)
#define setbit0(n,i) ((n)&(~(1LL<<(i))))
#define setbit1(n,i) ((n)|(1LL<<(i)))
#define togglebit(n,i) ((n)^(1LL<<(i)))
#define lastone(n) ((n)&(-(n)))
#define read freopen("debug\\in.txt","r",stdin)
#define write freopen("debug\\out.txt","w",stdout)
#define fi first
#define se second
#define getI(a) scanf("%d",&a)
#define getII(a,b) scanf("%d%d",&a,&b)
#define PI (acos(-1))
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD (1000000007)
#define asz 500005
#define pb push_back
#define ppf pop_front
#define ppb pop_back
#define pf push_front
ll a[500005];
int main() {
    ll n, i, j, k, l, m;
    ll t;
    scanf("%lld",&n);
    int flag=1;
    for(i=1;i<=n;i++){
        scanf("%lld",&m);
        if(m%2==0&&m%3!=0&&m%5!=0){
            flag=0;
        }
    }
    if(flag)
        printf("APPROVED");
    else
        printf("DENIED");
    return 0;
}

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

using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;

ll dp[101][4][4][4];

bool chack(int i, int j, int k, int t){

    bool res = true;
    if((i == 0  && j == 1 && k == 2) || (j == 0 && k == 1 && t == 2))res = false;
    swap(i, j);
    if((i == 0  && j == 1 && k == 2) || (j == 0 && k == 1 && t == 2))res = false;
    swap(i, j);
    swap(j, k);
    if((i == 0  && j == 1 && k == 2) || (j == 0 && k == 1 && t == 2))res = false;
    swap(j, k);
    swap(k, t);
    if((i == 0  && j == 1 && k == 2) || (j == 0 && k == 1 && t == 2))res = false;
    return !res;
}



int main()
{
    int n;
    cin >> n;
    memset(dp, 0, sizeof(dp));
    dp[0][3][3][3] = 1;

    for(int i = 0; i < n; i++){
        
        for(int j = 0; j < 4; j++){

            for(int k = 0; k < 4; k++){

                for(int t = 0; t < 4; t++){

                    for(int l = 0; l < 4; l++){

                        if(chack(j,k,t,l))continue;
                        dp[i + 1][k][t][l] += dp[i][j][k][t];
                        dp[i + 1][k][t][l] %= mod;
                    }
                }
            }
        }
    }

    ll ans = 0;

    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            for(int k = 0; k < 4; k++){
                ans += dp[n][i][j][k];
                ans %= mod;
            }
        }
    }
    cout << ans << endl;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  string s;
  cin >> s;
  if (s.back() == 's') s += "es";
  else s += "s";
  cout << s << '\n';
  return (0);
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll inf=1000000007;
const ll maxinput=10005;
const ll mod=998244353;
#define mp make_pair
ll n,k,mat[55][55];
ll tempmat[55][55];
void multiply(ll mat1[55][55],ll mat2[55][55])
{
    ll temp[55][55];
    for(ll i=0;i<n;i++)
    {
        for(ll j=0;j<n;j++)
        {
            temp[i][j]=0;
            for(ll k=0;k<n;k++)
                temp[i][j]+=mat1[i][k]*mat2[k][j],temp[i][j]%=inf;
        }
    }
    for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
            tempmat[i][j]=temp[i][j]%inf;
}
void power(ll k)
{
    if(k==1)
        return;

    power(k/2);
    multiply(tempmat,tempmat);
    if(k%2==1)
        multiply(tempmat,mat);

}
int main()
{
    memset(tempmat,0,sizeof(tempmat));
    memset(mat,0,sizeof(mat));
    cin>>n>>k;
    for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
            cin>>mat[i][j],tempmat[i][j]=mat[i][j];

    power(k);
    ll ans=0;
    for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
            ans+=tempmat[i][j],ans%=inf;

    cout<<(ans+inf)%inf<<"\n";

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include<map>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
vector<int> a;
int main(){
	int a[] = {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 n;
 	cin >> n;
	cout << a[n-1] << endl;
}


Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d %d %d", $an, $bn, $mn);
$as=explode(' ',trim(fgets(STDIN)));
$bs=explode(' ',trim(fgets(STDIN)));
$res = min($as) + min($bs);
for ($i=0;$i<$mn;$i++) {
  fscanf(STDIN, "%d %d %d", $ai, $bi, $c);
  $d = $as[$ai-1] + $bs[$bi-1] - $c;
  if ($d < $res) $res = $d;
}
echo $res;

Measured memory_bytes: 20980
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector< tuple< string , int , int > >v;
  for(int i = 0 ; i < n ; i++){
	string x ;
    int y;
    cin >> x >> y;
    v.push_back(make_tuple(x , -y , i + 1));
  }
  sort(v.begin() , v.end() );
  for(int i = 0 ; i < n ; i++){
	cout << get<2>(v[i]) << endl;
  }
  return 0;
}

Measured memory_bytes: 256
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
const int nax=57;
ll mod;

int n=50;

ll pot[nax][nax];

ll wyn;

void ff()
{
	fflush(stdout);
}

int pyt(int a, int b, int x, int y)
{
	printf("? %d %d %d %d\n", a, x, b, y);
	ff();
	int v;
	scanf("%d", &v);
	return v;
}

int los(int a, int b)
{
	return (rand()%(b-a+1))+a;
}

void szuk(int a, int b, int x, int y, int w)
{
	if (!w)
		return;
	if (a==b && x==y)
	{
		wyn+=pot[a][x];
		return;
	}
	if (a!=b)
	{
		//~ int s=(a+b)>>1;
		int s=los(a, b-1);
		int p=pyt(a, s, x, y);
		szuk(a, s, x, y, p);
		szuk(s+1, b, x, y, w-p);
	}
	else
	{
		//~ int s=(x+y)>>1;
		int s=los(x, y-1);
		int p=pyt(a, b, x, s);
		szuk(a, b, x, s, p);
		szuk(a, b, s+1, y, w-p);
	}
}

int main()
{
	int szit;
	scanf("%d%d%d%lld", &szit, &szit, &szit, &mod);
	ll trz=1;
	for (int i=0; i<n; i++)
	{
		for (int j=0; j<n; j++)
		{
			pot[i][j]=trz;
			trz=(trz*2)%mod;
		}
	}
	szuk(0, n-1, 0, n-1, 250);
	printf("! %lld\n", wyn%mod);
	ff();
	return 0;
}


Measured memory_bytes: 720
#include<bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pb push_back

using namespace std;

int n;

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


Measured memory_bytes: 3636
#include <stdio.h>

int data[110];

void BinaryInsertSort(int i)
{
	int left, mid, right, j;
	int insert = data[i], tmp;
	
	left = 0;
	right = i;
	while (left < right){
		mid = (left + right) / 2;
		if (data[mid] < insert){
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	for (j = left; j <= i; j++){
		tmp = insert;
		insert = data[j];
		data[j] = tmp;
	}
}

int main(void)
{
	int n, i, j;
	
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%d", &data[i]);
	}
	for (i = 0; i < n; i++){
		BinaryInsertSort(i);
		for (j = 0; j < n - 1; j++){
			printf("%d ", data[j]);
		}
		printf("%d\n", data[n - 1]);
	}
	
	return (0);
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(a) a.begin(),a.end()
typedef long long ll;
#define INF 1<<30

int main()
{
    int X,Y,Z;
    cin >> X >> Y >> Z;
    int Q = X/(Y+Z);
    int R = X%(Y+Z);
    if(R>=Z)cout << Q << endl;
    else cout << Q-1 << endl;
    return 0;
}

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

const int mod = 998244353;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int pow(int a, int b, int res = 1) {
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
	return res;
}
const int MAXN = 16385;
int f[MAXN];
int fac[MAXN], inv[MAXN];
int C(int a, int b) { return a < b ? 0 : (LL) fac[a] * inv[b] % mod * inv[a - b] % mod; }
int rev[MAXN], wn[MAXN], wt[MAXN], lim, dig;
void init(int sz) {
	lim = 1, dig = -1;
	while (lim < sz) lim <<= 1, ++dig;
	for (int i = 0; i != lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << dig;
	const int Wn = pow(3, (mod - 1) / lim); *wn = 1;
	for (int i = 1; i <= lim; ++i) wn[i] = mul(wn[i - 1], Wn);
}
void NTT(int * A, int typ) {
	for (int i = 0; i != lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
	for (int mid = 1; mid != lim; mid <<= 1) {
		const int Wn = lim / mid / 2;
		for (int i = 0, W = 0; i != mid; ++i, W += Wn)
			wt[i] = wn[typ == 1 ? W : lim - W];
		for (int k = 0; k != lim; k += mid << 1) {
			const int * W = wt;
			for (int l = 0; l != mid; ++l) {
				const int X = A[l + k], Y = mul(*W++, A[l + k + mid]);
				reduce(A[l + k] = X + Y - mod);
				reduce(A[l + k + mid] = X - Y);
			}
		}
	}
	if (typ == -1) {
		const int liminv = pow(lim, mod - 2);
		for (int i = 0; i != lim; ++i) A[i] = mul(A[i], liminv);
	}
}
int A[MAXN], B[MAXN];
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i != MAXN; ++i) {
		fac[i] = mul(fac[i - 1], i);
		inv[i] = mul(inv[mod % i], mod - mod / i);
	}
	for (int i = 2; i != MAXN; ++i) inv[i] = mul(inv[i - 1], inv[i]);
	int n, m; std::cin >> n >> m;
	init(n * 2 + 2);
	for (int i = 1; i <= n; ++i) B[i] = inv[i + 2];
	NTT(B, 1);
	f[0] = 1;
	for (int i = 1; i <= m; ++i) {
		memset(A, 0, lim << 2);
		for (int j = 0; j <= n; ++j) A[j] = mul(f[j], inv[j]);
		NTT(A, 1);
		for (int j = 0; j != lim; ++j) A[j] = mul(A[j], B[j]);
		NTT(A, -1);
		for (int j = 0; j <= n; ++j) A[j] = mul(A[j], fac[j + 2]);
		for (int j = 0; j <= n; ++j)
			reduce(A[j] += mul(f[j], C(j, 2) + j + 1) - mod);
		memcpy(f, A, n + 1 << 2);
	}
	int ans = 0;
	for (int i = 0; i <= n; ++i)
		reduce(ans += mul(f[i], C(n, i)) - mod);
	std::cout << ans << std::endl;
	return 0;
}


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

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n+1) cin>>a[i];
    vector<int> b(n);
    rep(i,n) cin>>b[i];
    
    long long ans = 0;
    rep(i,n){
        int t = min(a[i],b[i]);
        ans += t;
        b[i] -= t;
        t = min(a[i+1],b[i]);
        ans += t;
        a[i+1] -= t;
        
    }
    cout << ans << endl;
    
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(){
    int a,b,c,K,sum=0;
    cin>>a>>b>>c>>K;
    if(K-a<=0)cout<<K<<"\n";
    else if(K-a-b<=0)cout<<a<<"\n";
    else cout<<a+(K-a-b)*-1<<"\n";
}

Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;
#define INF 1e9;
int main(){
  int N,K; cin >> N >> K;
  vector<ll> h(N);
  for(int i = 0;i < N;i++)cin >> h[i];

  sort(h.begin(),h.end());

  ll ans = INF;
  for(int i = 0;i < N;i++){
    if(i + K - 1 < N){
      ans = min(ans,h[i + K - 1] - h [i]);
    }
    else break;
  }

  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VV(T, a, b, c) vector<vector<T>>(a, vector<T>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define VVV(T, a, b, c, d)                                                     \
  vector<vector<vector<T>>>(a, vector<vector<T>>(b, vector<T>(c, d)))
#define SP(a) setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

ll GCD(ll a, ll b) {
  if (b == 0)
    return a;
  return GCD(b, a % b);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll A, V, B, W, T;
  cin >> A >> V >> B >> W >> T;
  ll D = abs(A - B);

  if (W >= V)
    cout << "NO" << endl;
  else if (D > (V - W) * T)
    cout << "NO" << endl;
  else
    cout << "YES" << endl;

  return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0, i_len = n; (i) < (i_len); ++(i))
#define repp(i,n) for(int (i) = 1, i_len = n; (i) <= (i_len); ++(i))
#define per(i,n) for(int (i) = n-1; (i) >= 0; --(i))
#define perr(i,n) for(int (i) = n; (i) > 0; --(i))
#define sz(x) ((int)(x).size())
#define popcnt __builtin_popcount
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).begin(),(v).end(),greater<>()
#define debug(x) cerr << #x << ':' << x << '\n'
#define Pi 3.1415926535
#define MOD 1000000007
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
template<class T,class S> inline bool chmax(T& a, S b){if(a<b){a = b; return true;} return false;}
template<class T,class S> inline bool chmin(T& a, S b){if(a>b){a = b; return true;} return false;}
template<class T> T gcd(T a, T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/gcd(a,b);}
void yes(){cout << "Yes" << '\n';}
void no(){cout << "No" << '\n';}

int solve(){
    int x[5];
    rep(i,5) cin >> x[i];
    rep(i,5){
        if(x[i] == 0) cout << i+1 << endl;
    }


    return 0;
}

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


Measured memory_bytes: 3656
package main

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

func main() {
	X, Y, Z := ReadInt(), ReadInt(), ReadInt()
	fmt.Println(Z, X, Y)
}

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) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


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

int main()
{
  int64_t N, T;
  cin >> N >> T;
  vector<int64_t> t(N);
  for (auto&& e : t) cin >> e;
  int64_t ans = 0;
  for (int i = 0; i < N; i++) {
    ans += i == N - 1 ? T : min(T, t[i + 1] - t[i]);
  }
  cout << ans << endl;
}


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

int main(){
  int n;
  
  cin >> n;
  
  int ans = 0;
  int maxP = 0;
  for(int i=0; i<n; i++){
    int p;
    cin >> p;
    ans += p;
    maxP = max(maxP, p);
  }
  cout << ans - maxP/2 << endl;
  return 0;
}

Measured memory_bytes: 256
using System;
class Program
{
  static void Main(string[] args)
  {
    var n=Read();
    long sum=0, max=0;
    for(var i=0;i<n;i++){
      var p=Read();
      sum+=p;
      max=(p>max)?p:max;
    }
    Write(sum-(max/2));
  }

  static void Write(string s) { Console.WriteLine(s); return; }
  static void Write(long n) { Console.WriteLine(n.ToString()); return; }
  static string ReadStr() { return Console.ReadLine(); }
  static string[] ReadStrs() { return Console.ReadLine().Split(' '); }
  static long Read() { return long.Parse(Console.ReadLine()); }
  static long[] Read(long n) {
    long[] p = new long[n];
    string[] t = Console.ReadLine().Split(' ');
    for(long i = 0; i < n; i++) { p[i] = long.Parse(t[i]); }
    return p;
  }
  static long abs(long n) { return (n > 0) ? n : -n; }
  static long gcd(params long[] n) { long p = n[0]; for (long i = 1; i < n.Length; i++) { p = gcd(p, n[i]); } return p; }
  static long gcd(long a, long b) { return (a==0)?b:gcd(b % a, a); }
  static long lcm(params long[] n) { long p = n[0]; for (long i = 1; i < n.Length; i++) { p = lcm(p, n[i]); } return p; }
  static long lcm(long a, long b) { return a * b / gcd(a, b); }
  static long max(params long[] n) { long p = n[0]; for (long i = 1; i < n.Length; i++) { p = (p>n[i])?p:n[i]; } return p; }
  static long min(params long[] n) { long p = n[0]; for (long i = 1; i < n.Length; i++) { p = (p<n[i])?p:n[i]; } return p; }
  static void YN(bool t) { Console.WriteLine(t ? "YES" : "NO"); }
  static void Yn(bool t) { Console.WriteLine(t ? "Yes" : "No"); }
  static void yn(bool t) { Console.WriteLine(t ? "yes" : "no"); }
  static string clip(string s, int start, int count) {
    if (start + count < s.Length) { s = s.Remove(start + count); }
    if (start > 0) { s = s.Remove(0, start); }
    return s;
  }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
long long inf=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};
 
int main(){
  string a,b;
  cin>>a;
  cin>>b;
  if(a.size()>b.size()){
    cout<<"GREATER"<<endl;
    return 0;
  }else if(a.size()<b.size()){
    cout<<"LESS"<<endl;
    return 0;
  }else{
    REP(i,a.size()){
      if(a[i]>b[i]){
        cout<<"GREATER"<<endl;
        return 0;
      }else if(a[i]==b[i]){
        continue;
      }else{
        cout<<"LESS"<<endl;
        return 0;
      }
    }
  }
  cout<<"EQUAL"<<endl;
  return 0;
}

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

using namespace std;

typedef long long ll;

const int MOD = 1000000007;

ll f[200000], f_inv[200000];

ll modpow(ll x, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w;
    cin >> h >> w;
    f[0] = 1;
    f_inv[0] = 1;
    for (int i = 1; i <= h + w - 2; i++) {
        f[i] = f[i - 1] * i % MOD;
        f_inv[i] = modpow(f[i], MOD - 2);
    }
    int a, b;
    cin >> a >> b;
    ll ans = 0;
    int x1 = h + b - a - 1;
    int x2 = h + w - x1 - 2;
    if (h - a < w - b) {       
        for (int i = 0; i < h - a; i++) {
            ll tmp1 = (f[x1] * f_inv[i]) % MOD * f_inv[x1 - i] % MOD;
            ll tmp2 = (f[x2] * f_inv[h - i - 1]) % MOD * f_inv[x2 - h + i + 1] % MOD;
            ans = (ans + tmp1 * tmp2 % MOD) % MOD;
        }
    } else {
        for (int i = 0; i < w - b; i++) {
            ll tmp1 = (f[x1] * f_inv[w - i - 1]) % MOD * f_inv[x1 - w + i + 1] % MOD;
            ll tmp2 = (f[x2] * f_inv[i]) % MOD * f_inv[x2 - i] % MOD;
            ans = (ans + tmp1 * tmp2 % MOD) % MOD;
        }        
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
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; }

int main(void) {
    int k,x;
    cin>>k>>x;
    int left=max(-1000000,x-k+1);
    int right=min(1000000,x+k-1);
    for(int i=left;i<=right;i++){
        cout<<i<<" ";
    }
    cout<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

//*
//プラキュー（二分ヒープ）（最低限バージョン）
//int PQhikaku(int i,int j);//jの方が優先度が高いならtrueを返す
int PQhikaku(ll*heap,int i,int j){return heap[i]<heap[j];}
void heap_utod(ll*heap,int n){
	if(2*n>heap[0])return;
	int rflag=(2*n+1<=heap[0])&&(PQhikaku(heap,2*n,2*n+1));
	if(PQhikaku(heap,n,2*n+rflag)){
		ll temp=heap[2*n+rflag];
		heap[2*n+rflag]=heap[n];
		heap[n]=temp;
		heap_utod(heap,2*n+rflag);
	}
}
void heap_dtou(ll*heap,int n){
	if(n==1||PQhikaku(heap,n,n/2))return;
	ll temp=heap[n];
	heap[n]=heap[n/2];
	heap[n/2]=temp;
	heap_dtou(heap,n/2);
}
ll PQpop(ll*heap){
	ll rr=heap[1];
	heap[1]=heap[heap[0]--];
	heap_utod(heap,1);
	return rr;
}
void PQpush(ll*heap,ll n){
	heap[++heap[0]]=n;
	heap_dtou(heap,heap[0]);
}
//*/

ll a[200010];
ll h[200010];
int main(){
	ll n,m;
	scanf("%lld%lld",&n,&m);
	rep(i,0,n)scanf("%lld",a+i);
	sortdown(a,n);
	
	ll sum=0;
	rep(i,0,m){
		int t;
		scanf("%d",&t);
		sum+=t;
		PQpush(h,t);
	}

	ll ans=0,cnt=0;
	rep(i,0,n){
		while(h[0]&&h[1]>a[i]){
			sum-=PQpop(h);
			cnt++;
		}
		ans+=cnt*a[i]+sum;
	}
	printf("%lld\n",ans);
}


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

using namespace std;

#ifdef KACTL
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
#endif
#define all(x) begin(x), end(x)

using ll = int64_t;
using ld = long double;
using pii = pair<int32_t, int32_t>;
using vi = vector<int32_t>;

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

    string s;
    cin >> s;
    vi m(2019, 0);
    m[0] = 1;

    // p[i] 10^-i = p[j] * 10^-j
    // p[i] * 202^i = p[j] * 202^j

    ll ans = 0;
    int cur = 0;
    int b = 1;
    for (char c : s) {
        cur = (10 * cur + c - '0') % 2019;
        ans += m[(b * cur) % 2019]++;

        b = 202 * b % 2019;
    }

    cout << ans << endl;

    return 0;
}


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

xorsum = 0
right = 0
ans = 0

for left in range(N):
    while right < N and xorsum+A[right]==xorsum^A[right]:
        xorsum += A[right]
        right += 1
    ans += right-left
    if left==right:
        right += 1
    else:
        xorsum -= A[left]

print(ans)

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

using namespace std;

#define int long long
#define fw(i,a,b) for (int i = a; i <= b; ++i)
#define bw(i,a,b) for (int i = a; i >= b; --i)

const int N = 1e4 + 5;
int n, a[N], b[N], cnt1, cnt2;

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    fw(i, 1, n) cin >> a[i];
    fw(i, 1, n) cin >> b[i];

    fw(i, 1, n) {
        if(a[i] - b[i] > 0) cnt1 += a[i] - b[i];
        else cnt2 += (b[i] - a[i]) / 2;
    }

    if(cnt1 > cnt2) return cout << "No", 0;
    cout << "Yes";

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9 + 7, MOD = 1e9 + 7;
const long long LINF = 1e18;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
	string s;
	int n, cnt = 0;
	cin >> s >> n;
	if (s.size() == 1) {
		cout << s << endl;
		return 0;
	}
	vector<int> Cmp[26];
	for (int i = 0; i < s.size(); i++) {
		for (int j = 0; j < 26; j++) {
			if (s[i] == 'a' + j) {
				Cmp[j].push_back(i);
			}
		}
	}
	map<string, int> S;
	for (int i = 0; i < 26; i++) {
		if (S.size() < n) {
			for (int j = 0; j < Cmp[i].size(); j++) {
				for (int k = 1; k <= 5; k++) {
					S[s.substr(Cmp[i][j], k)] = 1;
				}
			}
		} else {
			break;
		}
	}
	// for (int i = 0; i < 26; i++) {
	// 	if (S[i].size()) {
	// 		sort(S[i].begin(), S[i].end());
	// 	}
	// }
	// for (int i = 0; i < 26; i++) {
	// 	for (int j = 0; j < S[i].size(); j++) {
	// 		cout << "i: " << i << " j: " << S[i][j] << endl;
	// 	}
	// }
	//vector<string> ans;
	// for (int i = 0; i < 26; i++) {
	// 	for (int j = 0; j < S[i].size(); j++) {
	// 		if (j) {
	// 			if (S[i][j] != S[i][j - 1]) {
	// 				ans.push_back(S[i][j]);
	// 			} else {
	// 				continue;
	// 			}
	// 		} else {
	// 			ans.push_back(S[i][j]);
	// 		}
	// 	}
	// }
	// for (auto i : S) {
	// 	cout << i.first << endl;
	// }
	int tmp = 0;
	for (auto i : S) {
		if (i.second) {
			tmp++;
			if (tmp == n) {
				cout << i.first << endl;
				return 0;
			}
		}
	}
	return 0;
}

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

#define MAX 25
#define NIL -1

struct Node{
    int p, l, r;
};

Node T[MAX];
int n, D[MAX], H[MAX];

void print(int i){
    cout << "node " << i << ": ";

    cout << "parent = " << T[i].p << ", ";

    cout << "sibling = ";
    if(T[i].p == NIL) cout << "-1, ";
    else if(T[T[i].p].l != i) cout << T[T[i].p].l << ", ";
    else cout << T[T[i].p].r << ", ";

    cout << "degree = ";
    int deg = 0;
    if(T[i].l != NIL) deg++;
    if(T[i].r != NIL) deg++;
    cout << deg << ", ";

    cout << "depth = " << D[i] << ", ";

    cout << "height = " << H[i] << ", ";

    if(T[i].p == NIL) cout << "root" << endl;
    else if(T[i].l == NIL && T[i].r == NIL) cout << "leaf" << endl;
    else cout << "internal node" << endl;

}

void setDepth(int i, int p){
    if(i == NIL) return;
    D[i] = p;
    setDepth(T[i].l, p+1);
    setDepth(T[i].r, p+1);
}

int setHeight(int i){
    int h1 = 0, h2 = 0;
    if(T[i].l != NIL) h1 = setHeight(T[i].l) + 1;
    if(T[i].r != NIL) h2 = setHeight(T[i].r) + 1;
    return H[i] = h1 > h2? h1 : h2;
}

int main(){
    cin >> n;
    //init
    rep(i,n) T[i].p = T[i].l = T[i].r = NIL;

    //make binary tree
    int id, left, right;
    rep(i,n){
        cin >> id >> left >> right;
        T[id].l = left;
        T[id].r = right;
        if(left != NIL) T[left].p = id;
        if(right != NIL) T[right].p = id;
    }
    //search for root
    int root;
    rep(i,n) if(T[i].p == NIL) root = i;

    setDepth(root, 0);
    setHeight(root);

    rep(i,n){
        print(i);
    }

    return 0;

}


Measured memory_bytes: 3120
#include <iostream>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdarg>
#include <set>
#include <limits>
#include <iomanip>

using namespace std;
#define INF 2e9 + 9
#define MOD 1000000007
#define ALL(v) v.begin() , v.end()
#define Int int64_t
#define pll pair<Int,Int>
template<class T> using pql = priority_queue<T, vector<T>>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
#define ll(n) Int n; cin >> n;
#define LL(...) Int __VA_ARGS___; cin >> __VA_ARGS___;
#define OUT(...) cout << __VA_ARGS___;
#define RP(n, i, s) for(Int i = s ;i < n ;i++)
#define REP(n, i) for (Int i = 0; i < n; i++)
#define REPe(n, i) for (Int i = 1; i <= n; i++)
#define RPe(n, i, s) for (Int i = s; i <= n; i++)
#define upd_max(maxer, updater) if (maxer < updater) maxer = updater;
#define upd_min(miner, updater) if (miner > updater) miner = updater;

void ansYes(bool flag){
    if (flag) cout << "Yes" << endl; else  cout << "No" << endl;
}

void ansYES(bool flag){
    if (flag) cout << "YES" << endl; else  cout << "NO" << endl;
}

struct node {
    Int to;
    Int length;
};


vector<Int> divisor(Int n) {
    vector<Int> ret;
    for (Int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    return (ret);
}

/*
vector<vector<int>> to;
vector<int> flag;
vector<int> c;


Int dfs(int from, int mae) {
    flag[from] = 1;
    Int mini = 0;
    for (auto next : to[from]) {
        if (next == mae) continue;
        if (flag[next] == 1) {
            return -1;
        } else {
            mini = min(mini, dfs(next, from));
        }
    }
    return mini;
}*/

int dx8[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

int nanko(string s,Int n,Int i){
    Int length = min(n - i - 1,i);
    Int ans = 0;
    for (int k = i-length;k < i;k++){
        if (s.at(k) == 'R' && s.at(i +  (i - k) == 'B')) ans++;
    }
    return ans;
}


int main() {
    Int n, m;
    cin >> n >> m;
    Int sum = 0;
    REP(m,i){
        Int x;
        cin >> x;
        sum += x;
    }
    if (n >= sum) {
        cout << n - sum << endl;
    }else{
        cout << -1 << endl;
    }
}

Measured memory_bytes: 3636
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007; // 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
/*-------------------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int a, b, c; cin >> a >> b >> c;
  cout << ((a <= c && c <= b) || (b <= c && c <= a) ? "Yes\n" : "No\n");
  return 0;
}


Measured memory_bytes: 256