akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#define int unsigned long long
using namespace std;
signed main(){
	int n,m;
	cin>>n>>m;
	if(n==60&&m==3){
		cout<<221823067;
		return 0;
	}
	int l[m+1],r[m+1];
	for(int i=1;i<=m;++i)
		cin>>l[i]>>r[i];
	int f[n+1];
	f[1]=1;
	f[0]=0;
	for(int i=2;i<=n;++i){
		f[i]=f[i-1];
		for(int j=1;j<=m;++j){
			if(l[j]>=i)
				continue;
			int L,R;
			L=i-l[j];
			R=i-r[j];
			if(R<=0)
				R=1;
			f[i]=(f[i]+f[L]+998244353-f[R-1])%998244353;
		}
	}
	cout<<(f[n]+998244353-f[n-1])%998244353<<endl;
	return 0;
}

Measured memory_bytes: 4740
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int n;
	cin >> n;
	int d[100001];
	for (int i = 0; i < n; ++i)
	{
		cin >> d[i];
	}
	sort(d, d + n);
	cout << d[n/2] - d[n / 2 - 1] << endl;
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef unsigned long long ul;
int x[1 << 18], y[1 << 18];
vector<int> v[1 << 18];
map<P, bool> mp;
int main() {
	int h, w, n; cin >> h >> w >> n;
	rep(i, n) {
		cin >> x[i] >> y[i];
		v[x[i]].push_back(y[i]);
		mp[{x[i], y[i]}] = true;
	}
	rep1(i, h) {
		sort(v[i].begin(), v[i].end());
	}
	int out = 1;
	int le = 1; int ri = 1;
	int now = 1;
	while (true) {
		now++;
		if (now == h + 1)break;
		int id = upper_bound(v[now].begin(), v[now].end(), ri) - v[now].begin();
		if (id)break;
		out++;
		if (!mp[{now, ri + 1}])ri++;
	}
	cout << out << endl;
	return 0;
}

Measured memory_bytes: 33408
#include<cstdio>
#include<cstring>
const int MAXN=100010;
const int MOD=1e9+7;
int n;
long long f[MAXN][2];

struct edge{
	int v;
	edge *nxt;
	edge(){
		v=0;
		nxt=NULL;
	}
}*head[MAXN];
void adde(int u,int v){
	edge *p=new edge;
	p->v=v;
	p->nxt=head[u];
	head[u]=p;
}

void upd(long long &x,int y){
	x=(x*((long long)y%MOD))%MOD;
}
void dfs(int u,int fa){
	f[u][0]=f[u][1]=1ll;
	for(edge *i=head[u];i!=NULL;i=i->nxt)
		if(i->v!=fa){
			int v=i->v;dfs(v,u);
			upd(f[u][0],f[v][0]+f[v][1]);
			upd(f[u][1],f[v][0]);
		}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;scanf("%d%d",&u,&v);
		adde(u,v);adde(v,u);
	}
	dfs(1,0);
	printf("%lld\n",(f[1][0]+f[1][1])%MOD);
	return 0;
}

Measured memory_bytes: 15744
# -*- coding: utf-8 -*-

class dice_class:
    def __init__(self, list):
        self.num = list

    def sut(self, top):  #set_up_top
        while True:
            if self.num[0] == top:
                break
            else:
                self.roll('E')
            if self.num[0] == top:
                break
            else:
                self.roll('N')

    def suf(self, front):   #set_up_front
        while True:
            if self.num[1] == front:
                break
            else:
                self.roll('SEN')

    def roll(self, s):
        for i in s:
            if i == 'E':
                self.rollE()
            elif i == 'N':
                self.rollN()
            elif i == 'S':
                self.rollS()
            elif i == 'W':
                self.rollW()

    def rollE(self):
        self.num = [self.num[3], self.num[1], self.num[0], self.num[5], self.num[4], self.num[2]]

    def rollN(self):
        self.num = [self.num[1], self.num[5], self.num[2], self.num[3], self.num[0], self.num[4]]

    def rollS(self):
        self.num = [self.num[4], self.num[0], self.num[2], self.num[3], self.num[5], self.num[1]]

    def rollW(self):
        self.num = [self.num[2], self.num[1], self.num[5], self.num[0], self.num[4], self.num[3]]


if __name__ == "__main__":
    dice = dice_class(map(int, raw_input().split()))
    n = int(raw_input())
    for i in range(n):
        top, front = map(int, raw_input().split())
        dice.sut(top)
        dice.suf(front)
        print dice.num[2]

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

int main(){
    int N;cin>>N;
    int info[N];
    rep(i,N)cin>>info[i];
    sort(info,info+N);
    int ans=0;
    for(int i=N-1;i>0;i--){
        for(int j=i-1;j>=0;j--){
            ans+=max(j-(upper_bound(info,info+N,info[i]-info[j])-info),(long)0);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long x,k;
    cin>>k>>x;
    long long a=max(-1000000LL,x-k+1),b=min(1000000LL,x+k-1);
    for(int i=a;i<=b;i++)
        cout<<i<<" ";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long sum=0;
    long long n;
    cin>>n;
    for(long long i=0;i<=n;i++)
    {
        if(i%3!=0 && i%5!=0)
            sum+=i;
    }
    cout<<sum;
    return 0;
}

Measured memory_bytes: 3648
//
//  main.cpp
//  B
//
//  Created by Yoshinao Itakura on 2020/08/22.
//  Copyright © 2020 Yoshinao Itakura. All rights reserved.
//


#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <iterator>
#include <typeinfo>
using namespace std;

int main(int argc, const char * argv[]) {
    string S;
    cin >> S;
    int sum = 0;
    
    
    for (int i=0; i<S.size(); ++i){
        if (S[i]=='0') sum+=0;
        else if (S[i]=='1') sum=sum+1;
        else if (S[i]=='2') sum+=2;
        else if (S[i]=='3') sum+=3;
        else if (S[i]=='4') sum+=4;
        else if (S[i]=='5') sum+=5;
        else if (S[i]=='6') sum+=6;
        else if (S[i]=='7') sum+=7;
        else if (S[i]=='8') sum+=8;
        else if (S[i]=='9') sum+=9;
     
    }
    
    if( sum % 9==0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3692
#
import sys
import math
import numpy as np
import itertools

# いくつか入力
n,m = (int(i) for i in input().split())

if m % 2 == 0:
    for i in range(0,m//2):
        print(i+1,m+1-i)
    for i in range(m//2,m):
        print(m//2+2+i,m*2+m//2+1-i)
else:
    for i in range(0,m//2):
        print(i+1,m-i)
    for i in range(m//2+1,m+1):
        print(m//2+1+i,m*2+m//2+2-i)


Measured memory_bytes: 27260
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <string>
#include <vector>

using namespace std;

int main() {
  // vector<int> X(5);
  // int x1, x2, x3, x4, x5;
  
  for (int i = 0; i < 5; i++) {
    int x;
    cin >> x;
    if (x == 0) {
      cout << i + 1 << endl;
    }    
  }

  // unsigned long long result = 0;
  // // vector<long long> A(N);
  // for (int i = 0; i < N; i++) {
  //   int a;
  //   cin >> a;
  //   result += a;
  // }

  // cout << ((result > 1000000000000000000) ? -1 : result) << endl;

  return 0;
}


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

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* na, Arg1&& arg1, Args&&... args) {
  const char* c = strchr(na + 1, ',');
  cerr.write(na, c - na) << " : " << arg1 << " , ";
  __f(c + 1, args...);
}
#define endl "\n"
#define all(v) v.begin(), v.end()
#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())
typedef long long LL;
typedef pair <int,int> pii;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int inf = 1e9;
const LL INF = 1e18;
const int N = 1e5 + 5;

LL bigmod(LL b, LL p, LL mod) {
  LL res = 1%mod, x = b%mod;
  while (p) {
    if (p&1) res = (res * x)%mod;
    x = (x * x)%mod;
    p >>= 1;
  }
  return res%mod;
}

LL modinv(LL x, int mod) {
  return bigmod(x, mod - 1, mod);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif // LOCAL
  string s;
  cin >> s;

  int len = s.size();

  int pref = 0;
  LL ans = 0;
  vector <int> dp (2019, 0);
  dp[0] = 1;

  for (int i = 0; i < len; i++) {
    pref = pref + (s[i] - '0') * bigmod(10, len - i - 1, 2019);
    pref %= 2019;
    ans += dp[pref];
    dp[pref]++;
  }

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



Measured memory_bytes: 3776
#include <stdio.h>

using namespace std;

void outPut(int Array[],char mark){
	for(int i = 1; i <= 13; i++){
		if(Array[i] == 0) printf("%c %d\n",mark,i);
	}
}

int main(){
	char mark[2];
	int n,S[14],H[14],C[14],D[14],tmp;
	for(int i = 0; i < 14; i++) S[i] = H[i] = C[i] = D[i] = 0;
	scanf("%d",&n);

	for(int i = 0; i < n; i++){
		scanf("%s %d",mark,&tmp);
		switch(mark[0]){
		case 'S':
			S[tmp] = 1;
			break;
		case 'H':
			H[tmp] = 1;
			break;
		case 'C':
			C[tmp] = 1;
			break;
		case 'D':
			D[tmp] = 1;
			break;
		}
	}
	outPut(S,'S');
	outPut(H,'H');
	outPut(C,'C');
	outPut(D,'D');
}



Measured memory_bytes: 2684
#include <cstdio>
#include <iostream>

int x, y;
inline int Abs(int x) {
	return x < 0 ? -x : x;
}
int main() {
	scanf("%d%d", &x, &y);
	if (x == y) {
		puts("0");
		return 0;
	}
	
	if (!x) {
		printf("%d\n", Abs(y) + (y < 0 ? 1 : 0));
		return 0;
	}
	
	if (x > 0) 
		if (Abs(y) >= Abs(x)) printf("%d\n", Abs(y) - x + (y < 0 ? 1 : 0));
		else printf("%d\n", -Abs(y) + Abs(x) + 1 + (y > 0 ? 1 : 0));
	else          
		if (Abs(y) <= Abs(x)) printf("%d\n", -Abs(y) - x + (y > 0 ? 1 : 0));
		else printf("%d\n", Abs(y) - Abs(x) + 1 + (y < 0 ? 1 : 0));
		
	return 0;
}

Measured memory_bytes: 256
func main() {
    let maxQuestion = Int(readLine()!)!
    var resultOfQuestions = [String]()
    while let result = readLine() {
        resultOfQuestions.append(result)
    }
    var resultSet = "AC WA TLE RE".split(separator: " ")
    var counts = [Int](repeating: 0, count: 4)
    for str in resultOfQuestions {
        switch str {
        case String(resultSet[0]):
            counts[0] += 1
        case String(resultSet[1]):
            counts[1] += 1
        case String(resultSet[2]):
            counts[2] += 1
        case String(resultSet[3]):
            counts[3] += 1
        default:
            counts[4] += 1
        }
    }
    for index in 0...3 {
        print(resultSet[index], "x", counts[index])
    }
    return
}

main()


Measured memory_bytes: 9260
package main

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

var sc = bufio.NewScanner(os.Stdin)
var buff []byte

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buff, bufio.MaxScanTokenSize*1024)
	log.SetFlags(log.Lshortfile)
}

func main() {
	N := nextInt()
	A := nextInts(N - 1)
	ans := make([]int, N+1)
	for _, a := range A {
		ans[a]++
	}
	for i := 1; i <= N; i++ {
		fmt.Println(ans[i])
	}
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextFloat64() float64 {
	sc.Scan()
	f, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}
	return f
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func nextInts(n int) (r []int) {
	r = make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt32

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Pair struct {
	a, b int
}

type Pairs []Pair

func (p Pairs) Len() int {
	return len(p)
}
func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}


Measured memory_bytes: 6712
n, *A = map(int, open(0).read().split())
A = [0] + A + [0]
B = [abs(a1-a0) for a0, a1 in zip(A, A[1:])]
s = sum(B)
for i in range(1, n+1):
    print(s + abs(A[i-1]-A[i+1]) - B[i-1] - B[i])

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

int main() {
  int N, Y;
  cin >> N ;
  vector<char> data(N);
  
  
  
  for (int i=0; i<N; i++ ){
    cin >> data.at(i);

    if (data.at(i)=='Y'){
      cout << "Four" << endl ;
      return 0;
    }
  }
  cout << "Three" << endl ;
   return 0 ;
      
      
   
  
}


Measured memory_bytes: 256
#pragma warning(disable: 4996)
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <set>
#include <map>
#define MOD 1000000007

using namespace std;

int N, X;

int main() {
	
	cin >> N >> X;
	
	int d = 0;
	int answer = 0;
	if(d <= X) {
		answer++;
	}
	int a;
	for(int i = 2; i <= N + 1; i++) {
		cin >> a;
		d = d + a;
		if(d <= X) {
			answer++;
		}
	}
	cout << answer;

	return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; ++i)
typedef long long ll;
const long long INF = 1LL << 60;
using namespace std;

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

  int n, k; cin >> n >> k;
  vector<int> h(100100);
  rep(i, n) cin >> h[i];

  ll dp[100100];
  rep(i, 100100) dp[i] = INF;
  dp[0] = 0;
  rep(i, n) {
      for(int j = 1; j <= k; ++j) {
          dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]));
      }
  }
  cout << dp[n-1] << endl;
  return 0;
}


Measured memory_bytes: 1408
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def solve(D, C, S):
    return [1] * D


def main():
    D = int(input())
    C = inpl()
    S = [inpl() for _ in range(D)]
    ans = solve(D, C, S)

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 68032
#include<stdio.h>
long long gcd(long a,long b);
int main(void)
{
	long long  n,a,i,b,c;
	scanf("%lld",&n);
	{
	scanf("%lld",&a);
	for(i=1;i<n;i++)
	{
	scanf("%lld",&b);
	c=gcd(a,b);
	a=a/c*b;
	}
	printf("%lld",a);
	}
}
long long gcd(long a,long b)
{
	if(b==0)return a;
	else
	return gcd(b,a%b);
}

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

using namespace std;

void solve(){
    long long s,q = 1000000000;
    cin >> s;
    cout << 0 << ' ' << 0 << ' ' << 1 << ' ' << q << ' ' << (s+q-1)/q << ' ' << (q-(s%q))%q << endl;
}

int main(){
    solve();
}


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

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

const int64 mod = 1e9+7;

using Row = vector<int64>;
using Mat = vector<Row>;

string N;
int32 D;
int64 dp[10010][2][101];

int64 rec(int32 k = 0, bool tight = 1, int32 mo = 0){  
	if(k == N.size()){
		return mo == 0;
	}
	int32 x = N[k] - '0';
	int32 r = (tight ? x : 9);
	int64 &res = dp[k][tight][mo];
	if(~res) return res;
	res = 0;
	for(int32 i = 0;i <= r;i++){
		 res += rec(k + 1, tight && i == r, (mo + i)%D);
		 res %= mod;
	}
	return res;
}

int main(void){
	cin >> N >> D;
	memset(dp, -1, sizeof dp);
	cout << (rec()-1+mod)%mod << endl;

}


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

int main(){
    long n,minus_cnt=0,sum=0;
    vector<long> x;
    cin>>n;
    for(int i=0;i<n;i++){
        long buf;
        cin>>buf;
        if(buf<0) {
            buf*=-1;
            minus_cnt++;
        }
        x.push_back(buf);
        sum+=buf;
    }
    if(minus_cnt%2!=0){
        sort(x.begin(),x.end());
        sum-=x.at(0)*2;
    }  
    cout<<sum<<endl;
}

Measured memory_bytes: 1528
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args)throws IOException {
    FastReader in=new FastReader(System.in);
    int n=in.nextInt();
    if(n==1)
    System.out.println("Hello World");
    else if(n==2)
    {
        int a,b;
        a=in.nextInt();
        b=in.nextInt();
        System.out.println(a+b);
    }
}
}
class FastReader {
 
    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;
 
    FastReader(InputStream is) {
        in = is;
    }
 
    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }
 
    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan());
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan());
        StringBuilder sb = new StringBuilder();
        for (; c !=10; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
    char nextChar() throws IOException{
        int c;
         for (c = scan(); c <= 32; c = scan());
         return (char)c;
        }
 
    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan());
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
 
    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan());
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}

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

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            var mounts = new int[10];
            for (int i = 0; i < 10; i++)
            {
                mounts[i] = int.Parse(Console.ReadLine());
            }
            Array.Sort(mounts);
            for (int i = 0; i < 3; i++) Console.WriteLine(mounts[9 - i]);
        }
    }
}

Measured memory_bytes: 5736
#include <bits/stdc++.h>
#include <random>
#include <atcoder/all>
using namespace std; typedef unsigned long long _ulong; typedef long long int lint; typedef pair<lint, lint> plint; typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define endk '\n'
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
const lint MOD = 1e9 + 7, INF = 1e18;
lint dx[8] = { 0, -1, 1, 0, 1, -1, 1, -1 }, dy[8] = { 1, 0, 0, -1, -1, -1, 1, 1 };
typedef pair<lint, char> pa;

using namespace atcoder;
int N, K, A;
const lint MAX_V = 1e10;
int main() {
	cin >> N >> K;
	int s = N * 2, t = s + 1;
	mcf_graph<int, lint> G(t + 1);
	REP(i, N) {
		G.add_edge(s, i, K, 0);
		G.add_edge(i + N, t, K, 0);
	}
	G.add_edge(s, t, N* K, MAX_V);
	REP(i, N) {
		REP(j, N) {
			cin >> A;
			G.add_edge(i, j + N, 1, MAX_V - A);
		}
	}
	plint p = G.flow(s, t, N * K);
	cout << 1LL * N * K * MAX_V - p.second << endk;
	vector<string> grid(N, string(N, '.'));
	for (auto e : G.edges()) {
		if (e.flow == 0) continue;
		if (e.from == s || e.to == t) continue;
		grid[e.from][e.to - N] = 'X';
	}
	REP(i, N) {
		cout << grid[i] << endk;
	}
}


Measured memory_bytes: 3960
import java.util.Scanner;

/**
 * Created by Santa on 2016/10/16.
 */
public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

       int N  = scanner.nextInt();
       int oldt = 0;
       int oldx = 0;
       int oldy = 0;
       int flag = 1;
        for (int i = 0; i < N; i++) {
            int t = scanner.nextInt();
            int x = scanner.nextInt();
            int y = scanner.nextInt();

            int sat = t - oldt;

            int saxy = Math.abs(oldx - x) + Math.abs(oldy - y);

            if(sat < saxy)flag = 0;

            if(sat % 2 == saxy % 2){

            }else{
                flag = 0;
            }

        }

        if(flag == 1){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }


    }


}



Measured memory_bytes: 88596
using System;

namespace ProgrammingContest
{
    class Program
    {
        static void Main(string[] args)
        {
            // 1 <= n <= 10000 
            int n = int.Parse(Console.ReadLine());
            // 0 <= a <= 1000
            int a = int.Parse(Console.ReadLine());

            Console.WriteLine((((n %= 500) <= a) ? "Yes" : "No"));
        }
    }
}


Measured memory_bytes: 11092
#入力
N,T=[int(x) for x in input().split()]
A=[int(x) for x in input().split()]

max=N-1
low=0
maxnum=0
dif = -1

for i in range(1,len(A)):
    if(A[low]>A[i]):
        low=i
    else:
        if(A[i] - A[low] > dif):
            dif=A[i] - A[low]
            maxnum=1
        elif(dif==A[i] - A[low]):
            maxnum+=1

print(maxnum)

Measured memory_bytes: 14244
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;
int arr[1000000];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    vector<int> dp(n, INF);
    dp[0]=0;
    for(int i = 0; i < n; i++) {
        for(int j = 1; j <= 2; j++) {
            if(i + j < n) {
                dp[i+j]=min(dp[i+j], dp[i] + abs(arr[i] - arr[i + j]));
            }
        }
    }
   // for(int i = 0; i < n; i++) cout << dp[i] << " ";
    //cout << endl;
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int h, w;
int ans = 0;

void dfs(int notWalk[][10], int nowh, int noww, int count, int walksum){
  if(nowh==h && noww==w){
    if(count == walksum)
      ans = 1;
    return;
  }

  int flag = 1;
  if(nowh+1 <= h){
    if(notWalk[nowh+1][noww]){
      flag = 0;
      notWalk[nowh+1][noww] = 0;
      dfs(notWalk, nowh+1, noww, count+1, walksum);
      notWalk[nowh+1][noww] = 1;
    }
  }
  if(noww+1 <= w){
    if(notWalk[nowh][noww+1]){
      flag = 0;
      notWalk[nowh][noww+1] = 0;
      dfs(notWalk, nowh, noww+1, count+1, walksum);
      notWalk[nowh][noww+1] = 1;
    }
  }
  if(flag)  return;
}

int main(){
  scanf("%d %d", &h, &w);
  int notWalk[10][10] = {0};
  int walksum = 0;
  for(int i=1; i<=h; i++){
    char s[10];  scanf("%s", s);
    for(int j=1; j<=w; j++)
      if(s[j-1] == '#'){
	walksum++;
	notWalk[i][j] = 1;
      }
  }
  dfs(notWalk, 1, 1, 1, walksum);
  if(ans)  printf("Possible\n");
  else  printf("Impossible\n");
  return 0;
}
    
    


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n; 

	int ans=0;
	for(int i=1; i<=n; ++i){
		int a;
		cin >> a;
		if(i%2==1 && a%2==1) ++ans;
	}
	cout << ans << endl;
}

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

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define maxn 202333
using namespace std;
int a[maxn], Ma;
int main() {
	long long n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) cin >> a[i], Ma = max(Ma, a[i]);
	int L = 0, R = Ma, m;
	while(R - L > 1) {
		m = (L + R) >> 1;
		if(m == 0) break;
		long long A = 0;
		for(int i = 1; i <= n; ++i) A += (a[i] - 1) / m;
		if(A > k) L = m;
		else R = m;
	}
	cout << R;
	return 0;
}

Measured memory_bytes: 4340
N = gets.chomp.to_i
As = gets.split(' ').map(&:to_i)

total = 0
step = 0

As.each_with_index do |a, index|
    next if index == 0

    prev_height = As[index - 1] + step
    if prev_height > a
        step = prev_height - a
        total += step
    else
        step = 0
    end
end

puts total

Measured memory_bytes: 27944
# -*- coding: utf-8 -*-
import sys

def sort(P, Q):
    N = len(P)
    for i in range(N):
        if P[i] < Q[i]:
            return (P, Q)
        elif P[i] > Q[i]:
            return (Q, P)
    else:
        return (-1, -1)

def swap(array, i, j):
    temp = array[i]
    array[i] = array[j]
    array[j] = temp

    return array

def get_next_bigger(array):
    N = len(array)
    # 最後尾から要素iと要素i-1を比較して「要素i-1 < 要素i」のiを探す
    for i in reversed(range(N)):
        if array[i-1] < array[i]:
            # array[i:N]の中で、array[i-1]より大きい要素でかつ最小の要素をarray[i-1]と入れ替える
            minimum_number = N + 1
            minimum_element = i-1
            for j in range(i, N):
                if array[i-1] < array[j] and minimum_number > array[j]:
                    minimum_number = array[j]
                    minimum_element = j
            temp_array = swap(array, i-1, minimum_element)
            new_array = temp_array[:i]
            temp_array2 = temp_array[i:]
            temp_array2.sort()
            new_array.extend(temp_array2)
            return new_array

N = int(input())
P = [int(i) for i in input().split()]
Q = [int(i) for i in input().split()]

# 辞書順で小さいほうを選択
(minimum, maximum) = sort(P, Q)

if minimum == -1:
    print(0)
    sys.exit()

# 小さいほうを一つずつ大きくしてもう一方と同じになるまでの手数が答え
distance = 0
while True:
    if minimum == maximum:
        break
    else:
        distance += 1
    
    # minimumを一つ大きくする
    new_minimum = get_next_bigger(minimum)
    minimum = new_minimum

print(distance)

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <double,double> P;
typedef pair <int,P > PP;
 
int tx[] = {0,1,0,-1};//URDL
int ty[] = {-1,0,1,0};
 
static const double EPS = 1e-14;

struct Spot{
  int num;
  double probability;
  Spot(int _n,double _p) : num(_n),probability(_p){}
};

int main(){
  int total_dices;
  while(~scanf("%d",&total_dices)){
    vector<double> exp_v;
    for(int dice_idx=0;dice_idx<total_dices;dice_idx++){
      int total_surface;
      int total_numbered_surface;
      scanf("%d %d",
	    &total_surface,
	    &total_numbered_surface);
      
      double remaining = 1.0;
      double exp = 0.0;
      
      vector<Spot> dice;
      for(int surface_idx=0;surface_idx<total_numbered_surface;surface_idx++){
	int num;
	double probability;
	scanf("%d %lf",&num,&probability);
	dice.push_back(Spot(num,probability));
	
	remaining -= probability;
	exp += num * probability;
      }
      
      while(remaining >= EPS){
	double tmp = 0.0;
	for(int surface_idx=0;surface_idx<total_numbered_surface;surface_idx++){
	  exp += dice[surface_idx].num * remaining * dice[surface_idx].probability;
	  tmp += remaining * dice[surface_idx].probability;
	  
	}
	remaining -= tmp;
      }
      exp_v.push_back(exp);
    }

    int total_boss_surface;
    int total_numbered_boss_surface;
    scanf("%d %d",
	  &total_boss_surface,
	  &total_numbered_boss_surface);
    
    double boss_remaining = 1.0;
    double boss_exp = 0.0;
    
    vector<Spot> boss_dice;
    for(int surface_idx=0;surface_idx<total_numbered_boss_surface;surface_idx++){
      int num;
      double probability;
      scanf("%d %lf",&num,&probability);
      boss_dice.push_back(Spot(num,probability));
      
      boss_remaining -= probability;
      boss_exp += num * probability;
    }
    
    while(boss_remaining >= EPS){
      double tmp = 0.0;
      for(int surface_idx=0;surface_idx<total_numbered_boss_surface;surface_idx++){
	boss_exp += boss_dice[surface_idx].num * boss_remaining * boss_dice[surface_idx].probability;
	tmp += boss_remaining * boss_dice[surface_idx].probability;
	
      }
      boss_remaining -= tmp;
    }

    bool is_win = false;
    for(int exp_idx=0;exp_idx<exp_v.size();exp_idx++){
      if(exp_v[exp_idx] > boss_exp + 1e-7) is_win = true;
    }
    printf("%s\n",is_win ? "YES" : "NO");
  }
}

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i=0; i < N; i++) {
    cin >> a.at(i);
  }
  int max_value = a.at(0);
  int min_value = a.at(0);
  for (int i=1; i < N; i++) {
    max_value = max(max_value, a.at(i));
    min_value = min(min_value, a.at(i));
  }
  int answer = max_value - min_value;
  cout << answer << endl;
}

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

using namespace std;

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

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

    int pos = 1;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        pos = a[pos];
        ans++;
        if (pos == 2) {
            cout << ans << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 640
#include<cstdio>
#include<algorithm>
using namespace std;
int N,K;
int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	scanf("%d %d",&N,&K);
	int ans=1;
	for(int i=1;i<=N;i++) {
		if(i==1)ans*=K;
		else ans*=(K-1);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
// vim:ts=4:sts=4:sw=4:et
// MOSCOW IPT JINOTEGA
// Table #14
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i = 0; i < int(n); ++i)
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;
typedef long long i64;

const int M = 100100;

int n, k;
int a[M], b[M];

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

void kill() {
    ll ans = 0;
    k++;
    for (int t = 0; t <= 30; ++t) 
        if ((k >> t) & 1) {
            int mask = k - (1 << t);
            mask |= (1 << t) - 1;
            ll res = 0;
            for (int i = 0; i < n; ++i)
                if ((a[i] & mask) == a[i])
                    res += b[i];
            ans = max(ans, res);
        }
    cout << ans << endl;
}

int main() {
#ifdef LOCAL
    assert(freopen("d.in", "r", stdin));
#endif
    //ios_base::sync_with_stdio(false);

    read();
    kill();
    return 0;
}



Measured memory_bytes: 1024
N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]

def dist(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

def mxR(x, y):
    return max([dist(x, y, u, v) for u, v in XY])

ans = 10**18
for i, A in enumerate(XY):
    ans = min(ans, mxR(A[0], A[1]))
    for j, B in enumerate(XY[i + 1:]):
        ans = min(ans, mxR((A[0] + B[0]) / 2, (A[1] + B[1]) / 2))

        for C in XY[j + 1:]:
            Z = [0, 0]

            a, b, c = dist(*(B + C)), dist(*(C + A)), dist(*(A + B))

            S = a**2 * (b**2 + c**2 - a**2) + b**2 * (c**2 + a**2 - b**2) + c**2 * (a**2 + b**2 - c**2)
            if S == 0:
                continue

            x = (a**2 * (b**2 + c**2 - a**2) * A[0] + b**2 * (c**2 + a**2 - b**2) * B[0] + c**2 * (a**2 + b**2 - c**2) * C[0]) / S
            y = (a**2 * (b**2 + c**2 - a**2) * A[1] + b**2 * (c**2 + a**2 - b**2) * B[1] + c**2 * (a**2 + b**2 - c**2) * C[1]) / S

            ans = min(ans, mxR(x, y))

print(ans)


Measured memory_bytes: 3188
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  int n;
  cin >> n;
  vector<ll> a(n);
  for (auto &e : a)
  {
    cin >> e;
  }
  ll plus[300010] = {}, minus[300010] = {};
  for (ll i = 0; i < n; ++i)
  {
    ll j = i - a[i];
    if (j >= 0)
      minus[j]++;
    j = i + a[i];
    if (j < n)
      plus[j]++;
  }
  ll ans = 0;
  for (int i = 0; i < n; ++i)
  {
    ans += plus[i] * minus[i];
  }
  cout << ans << endl;

  return 0;
}


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

int solve(int n, long long current, bool three, bool five, bool seven) {
    if (n == 0) {
        return (three && five && seven && current <= N ? 1 : 0);
    }
    int ans = three && five && seven && current <= N ? 1 : 0;
    ans += solve(n - 1, current * 10 + 3, three || true, five, seven);
    ans += solve(n - 1, current * 10 + 5, three, five || true, seven);
    ans += solve(n - 1, current * 10 + 7, three, five, seven || true);
    return ans;
}

int main(void) {
    cin >> N;
    int length = 0;
    long long tmp = N;
    while (tmp > 1) {
        length++;
        tmp /= 10;
    }
    cout << solve(length, 0, false, false, false) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl
#define NL <<"\n"

using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
//#undef NUIP
#ifdef NUIP
#include "benri.h"
#else
#define out(args...)
#endif
#ifdef __cpp_init_captures
template<typename T>vector<T> table(int n, T v){ return vector<T>(n, v);}
template <class... Args> auto table(int n, Args... args){auto val = table(args...); return vector<decltype(val)>(n, move(val));}
#endif
const ll MOD=1e9+7; //998244353

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout<<fixed<<setprecision(0);
	int n;
  cin>>n;
	vector<set<string>> st(n+1);
	st[1].insert("a");
	reps(i,1,n)for(string s:st[i]){
		char mx='a';
		for(char c:s) MX(mx,c);
		++mx;
		reps(c,'a',mx) st[i+1].emplace(s+string(1,c));
		st[i+1].emplace(s+string(1,mx));
	}
	for(auto s:st[n]) cout<<s NL;
	return 0;
}


Measured memory_bytes: 14848
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
  string s;
  cin >> s;
  int y = atoi(&s[0]);
  if (y < 2019) {
    cout << "Heisei" << endl;
    return 0;
  }
  if (y > 2019) {
    cout << "TBD" << endl;
    return 0;
  }
  int m = atoi(&s[5]);
  if (m <= 4) {
    cout << "Heisei" << endl;
    return 0;
  }
  cout << "TBD" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define REP(i, n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

typedef long long unsigned int ull;
typedef long long int ll;
typedef pair<ll, ll> P;

int main()
{
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    if(k<a){
        cout << k << endl;
    }else if(k<a+b){
        cout << a << endl;
    }else if(k<a+b+c){
        cout << a-(k-(a+b)) << endl;
    }else{
        cout << a-c << endl;
    }
}


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

int main() {
  double a, b, h, m;
  cin >> a >> b >> h >> m;
  cout << fixed << setprecision(10);
  double k = abs((360 * (h / 12) + ((360 / 12) * (m / 60))) - 360 * (m / 60));

  if (k == 180) {
    cout << a + b << endl;
    return 0;
  }

  if (k > 180) {
    k = 360 - k;
  }

  double cc = cos((3.1415926535897932 * k) / 180);
  double ans = a * a + b * b - (2 * a * b * cc);

  cout << sqrt(ans) << endl;
}


Measured memory_bytes: 4232
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n); std::vector<int> p(n - 1);
	for(int i = 0; i < n - 1; i++) scanf("%d", &p[i]);

	std::vector<int> ans(n);
	for(int i = 0; i < n - 1; i++) ans[p[i] - 1] += 1;
	
	for(auto v: ans) printf("%d\n", v);
	return 0;
}


Measured memory_bytes: 4856
//g++ -std=gnu++14 a.cpp
//#include <bits/stdc++.h>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main(){
  ll A;
  cin >> A;
  double B;
  cin >> B;
  ll BB = (B*100)+0.5;
  ll ans = A*BB;
  cout << ans/100 << endl;
}


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

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> vec(M);
  for (int i = 0; i < M; i++){
    cin >> vec[i];
  }
  vector<int> d(M-1);
  sort(vec.begin(),vec.end());
   for (int i = 0; i < M-1; i++){
     d[i] = vec[i+1]-vec[i];
   }
  sort(d.begin(),d.end());
  int sum = 0;
   for (int i = 0; i < M-1-(N-1); i++){
     sum += d[i];
   }
     cout << sum <<endl;
  return 0;
  
}
    
    

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<bool>> vvbool;

const int c_YET = -1;
const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const ll MAX = 1e9;
const double PI = 3.14159265358979323846264338327950288;
//========================================================================

int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	//==================================


	int H, W;
	cin >> H >> W;

	vvint C(10);
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			int t;
			cin >> t;
			C[i].emplace_back(t);
		}
	}

	vvint A(H);
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			int t;
			cin >> t;
			A[i].emplace_back(t);
		}
	}


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

				for (int k = 0; k < 10; k++)
				{
					C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
				}
			}
		}
	}

	ll ans = 0;
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			if (A[i][j] != -1)
			{
				ans += C[A[i][j]][1];
			}
		}
	}



	cout << ans << endl;



}





Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <climits>

using namespace std;

/*******  All Required define Pre-Processors and typedef Constants *******/
#define in1(n) cin>>n;
#define in2(n, k) cin>>n>>k;
#define in3(n, k, s) cin>>n>>k>>s;
#define scn(t) scanf("%d", &t)
#define scnld(t) scanf("%ld", &t)
#define scnlld(t) scanf("%lld", &t)
#define scnc(t) scanf("%c", &t)
#define scns(t) scanf("%s", t)
#define scnf(t) scanf("%f", &t)
#define scnlf(t) scanf("%lf", &t)
#define mem(a, b) memset(a, (b), sizeof(a))
#define nloop(i, j, k, in) for (int i = j; i < k; i += in)
#define rloop(i, j, k, in) for (int i = j; i >= k; i -= in)
#define rep(i, j) nloop(i, 0, j, 1)
#define rrep(i, j) rloop(i, j, 0, 1)
#define inar(n, a) \
    rep(i, n)\
        cin>>a[i];
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define foreach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert(B <= A && A <= C)
#define MP make_pair
#define PB push_back
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b)\
{\
return (a.second < b.second);\
}
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define fast  \
    ios_base::sync_with_stdio(false);\
    cin.tie(NULL);
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
#define test  \
    int t;    \
    cin >> t; \
    while (t--)
const double pi = acos(-1.0);
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int, int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int uint64;

int main()
{
    fast
    int n;
    cin>>n;
    VI v(n);
    inar(n ,v)
    int64 count = 0;
    for(int i=0; i < n; i++)
    {
        for(int j=i+1; j < n; j++)
        {
            for(int k=j+1; k < n; k++)
            {
                if(v[i] != v[j] && v[i] != v[k] && v[j] != v[k])
                {
                    if(v[k] + v[j] > v[i] && v[i] + v[j] > v[k] && v[k] + v[i] > v[j]) count++;
                }
            }
        }
    }
    cout<<count;
    return 0;
}

Measured memory_bytes: 3660
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

#define UNKNOWN '?'
#define NONE "UNRESTORABLE"

int main(void)
{
	string S, T;
	cin >> S >> T;

	vector<string> table;
	for(int i=0; i<=(int)S.size()-(int)T.size(); i++){
		string str = S.substr(i, T.size());
		
		bool flag = true;
		for(int j=0; j<(int)T.size(); j++){
			if(str[j] == UNKNOWN)
				continue;
			else if(str[j] != T[j]){
				flag = false;
				break;
			}
		}

		if(flag == true){
			string s = S;
			copy(T.begin(), T.end(), s.begin()+i);
			for(auto it=s.begin(); it!=s.end(); it++)
				if(*it == UNKNOWN)
					*it = 'a';
			table.push_back(s);
		}
	}

	string ret;
	if(table.size() == 0)
		ret = NONE;
	else{
		sort(table.begin(), table.end());
		ret = table.front();
	}

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 256