akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;

int n = 100001;

vector<bool> dp(n, false);
vector<int> sum(n, 0);

void Eratosthenes(){
    dp[1] = true;
    for(int i = 2; i < n; i++){
        if(dp[i]) continue;
        for(int j = i*2; j < n; j += i){
            dp[j] = true;
        }
    }
}

void MakeSum(){
    int count = 0;
    for(int i = 1; i < n; i++){
        if(!dp[i] && !dp[(i+1)/2]) count++;
        sum[i] = count;
    }
}

int main(){
    Eratosthenes();
    MakeSum();
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int l,r;
        cin >> l >> r;
        cout << sum[r] - sum[l-1] << endl;
    }
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {
  public static int H;
  public static int W;
  public static char[][] S;
  public static boolean[][] used;
  public static long black;
  public static long white;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    H = sc.nextInt();
    W = sc.nextInt();
    S = new char[H][W];
    used = new boolean[H][W];
    for (int i = 0; i < H; i++) {
      S[i] = sc.next().toCharArray();
    }
    for (int i = 0; i < H; i++) {
      Arrays.fill(used[i], false);
    }
    long ans = 0;
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        black = 0;
        white = 0;
        if (!used[i][j]) {
          dfs(i, j);
        }
        ans += black * white;
      }
    }
    System.out.println(ans);
  }

  public static void dfs(int i, int j) {
    if (used[i][j]) {
      return;
    }
    if (S[i][j] == '#') {
      black++;
    } else {
      white++;
    }
    used[i][j] = true;
    int[] dy = { -1, 0, 0, 1 };
    int[] dx = { 0, -1, 1, 0 };
    for (int d = 0; d < 4; d++) {
      int sy = i + dy[d];
      int sx = j + dx[d];
      if (0 <= sy && 0 <= sx && sy < H && sx < W) {
        if (S[i][j] != S[sy][sx] && !used[sy][sx]) {
          dfs(sy, sx);
        }
      }
    }
  }
}

Measured memory_bytes: 51700
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]


n=i1()
a=[0]+i2()+[0]
b=[]
c=0
d=[]
for i in range(n+1):
 b.append(abs(a[i]-a[i+1]))
 c+=b[-1]
 if i<n:d.append(abs(a[i]-a[i+2]))
for i in range(n):
 print(c-b[i]-b[i+1]+d[i])


Measured memory_bytes: 67052
from itertools import accumulate

N, constW = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
L = [[] for _ in range(4)]
for w, v in WV:
  w -= W0
  L[w].append(v)
L[0].sort(reverse=True)
L0 = [0] + list(accumulate(L[0]))
l0 = len(L0) - 1
L[1].sort(reverse=True)
L1 = [0] + list(accumulate(L[1]))
l1 = len(L1) - 1
L[2].sort(reverse=True)
L2 = [0] + list(accumulate(L[2]))
l2 = len(L2) - 1
L[3].sort(reverse=True)
L3 = [0] + list(accumulate(L[3]))
l3 = len(L3) - 1
ans = 0
for i in range(1, constW//W0 + 1):
  rest = constW - i*W0
  for j in range(min(rest//3, i, l3) + 1):
    rest1 = rest - 3*j
    for k in range(min(rest1//2, i-j, l2) + 1):
      rest2 = rest1 - 2*k
      for l in range(min(rest2, i-j-k, l1) + 1):
        temp = L3[j] + L2[k] + L1[l] + L0[min(l0, i-j-k-l)]
        ans = max(ans, temp)
print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define _GLIBCXX_DEBUG
int main()
{
    int n,k;
    cin>>n>>k;
    int d=0;
    while(n){
        n/=k;
        d++;
    }
    cout<<d<<endl;
}

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

int main(){
    string s, t;
    cin>>s>>t;
    int cnt = 0;
    for(int i = 0; i < 3; i++){
        if(s[i] == t[i]) cnt++;
    }
    cout<<cnt<<"\n";
    return 0;
}


Measured memory_bytes: 256
def check(goal, dist_data, start):
    dp_now = [0 for i in range(17000)]
    dp_now[start + 8500] = 1
    dp_next = [0 for i in range(17000)]

    for i in range(len(dist_data)):
        for j in range(len(dp_now)):
            if dp_now[j]:
                dp_next[j + dist_data[i]] = 1
                dp_next[j - dist_data[i]] = 1
        dp_now = dp_next
        dp_next = [0 for i in range(17000)]

    return dp_now[goal + 8500]


def main():
    data = input()
    goal = list(map(int, input().split()))
    data = data.split('T')
    move_dist = [len(ele) for ele in data]

    x_data = move_dist[2::2]
    y_data = move_dist[1::2]

    if check(goal[0], x_data, move_dist[0]) and check(goal[1], y_data, 0):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Measured memory_bytes: 132744
#x = [int(i) for i in input().split()]
n = int(input())
for i in range(1, n+1):
    cnt = 0
    if i % 3 == 0:
        print(" ",i,sep="",end="")
        cnt += 1
    elif cnt == 0:
        x = i
        while True:
            if x % 10 == 3:
                print(" ",i,sep="",end="")
                cnt += 1
                break
            elif x // 10 == 0:
                cnt += 1
                break
            else:
                x = x // 10
print("")


Measured memory_bytes: 6164
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    static void solve(InputReader in, PrintWriter out){
        char[] s = in.ns().toCharArray();
        if(s[0]=='7'||s[1]=='7'||s[2]=='7') out.println("Yes");
        else out.println("No");
    }

    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 32860
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n=0;
    scanf("%lld", &n);
    long long arr[100]={0};
    arr[0]=2;
    arr[1]=1;
    for(int i=2;i<=n;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    printf("%lld", arr[n]);
}

Measured memory_bytes: 256
d, g=map(int, input().split())
p_list=[]
c_list=[]
all_list=[]
for i in range(d):
    p, c=map(int, input().split())
    p_list.append(p)
    c_list.append(c)
    all_list.append(100*(i+1)*p+c)



answer=[]

for i in range(2**d):
    number=0
    sum_score=0
    flag=0
    used_number=[]
    for j in range(d):
        if (i>>j)&1:
            sum_score=sum_score+all_list[j]
            number=number+p_list[j]
            used_number.append(j)
    if sum_score>=g:
        answer.append(number)
    else:
        for k in range(d-1, -1, -1):
            if not k in used_number:
                for l in range(p_list[k]):
                    if sum_score+100*(k+1)*l>=g:
                        answer.append(number+l)
                        flag=1
                        break
            if flag:
                break

print(min(answer))


Measured memory_bytes: 43120
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_PTN_MAX		4096									// 最大パターン数

// 内部変数
static FILE *szpFpI;											// 入力
static int siBCnt;												// 箱数
static int si1Cost[D_PTN_MAX];									// 費用

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i, j;
	char lc1Buf[1024];

	// 箱数・鍵数 - 取得
	int liKCnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &siBCnt, &liKCnt);

	// 費用 - 初期化
	si1Cost[0] = 1;

	// 全開錠パターン
	int liAll = (1 << siBCnt) - 1;

	// 鍵 - 取得
	for (i = 0; i < liKCnt; i++) {

		// 費用・開錠数 - 取得
		int liCost, liOCnt;
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d", &liCost, &liOCnt);

		// 開錠パターン - 取得
		int liPtn = 0;
		for (j = 0; j < liOCnt; j++) {
			int liBNo;
			fscanf(szpFpI, "%d", &liBNo);
			liPtn += 1 << (liBNo - 1);
		}
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);

		// 鍵 - 加算
		for (j = 0; j < liAll; j++) {
			if (si1Cost[j] < 1) {
				continue;
			}

			// 鍵使用時
			int liCost2 = si1Cost[j] + liCost;
			int liPtn2 = j | liPtn;

			// コスト - 更新
			if (si1Cost[liPtn2] == 0 || si1Cost[liPtn2] > liCost2) {
				si1Cost[liPtn2] = liCost2;
			}
		}
	}

	return si1Cost[liAll] - 1;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// データ - 初期化
	memset(si1Cost, 0, sizeof(si1Cost));						// 費用

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 出力
	sprintf(lc1Buf, "%d\n", liRet);
	fOutLine(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    int a[2][1000];
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[0][i];
    for(int i=0;i<n;i++) cin>>a[1][i];
    int ans=0;
    
    for(int i=0;i<n;i++){
        int sum=0;
        for(int j=0;j<=i;j++){
            sum+=a[0][j];
        }
        for(int k=i;k<n;k++){
            sum+=a[1][k];
        }
        ans=max(sum,ans);
    }
    cout<<ans;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] p = new int[n];
		for(int i = 0; i < n; i++){
		    p[i] = sc.nextInt() - 1;
		}
		int[] c = new int[n];
		for(int i = 0; i < n; i++){
		    c[i] = sc.nextInt();
		}
		
		// 計算
		long result = Long.MIN_VALUE;
		boolean[] flg = new boolean[n];
		ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
		ArrayList<Long> sum = new ArrayList<Long>();
		for(int i = 0; i < n; i++){
		    if(flg[i]) continue;
		    ArrayList<Integer> list = new ArrayList<Integer>();
		    long temp = 0;
		    int index = p[i];
		    for(int j = 0; j < n; j++){
		        if(flg[index]) break;
		        flg[index] = true;
		        list.add(c[index]);
		        temp += c[index];
		        index = p[index];
		    }
		    lists.add(list);
		    sum.add(temp);
		    //System.out.println(list);
		    //System.out.println(sum);
		}
		
		for(int i = 0; i < lists.size(); i++){
		    ArrayList<Integer> list = lists.get(i);
		    long temp = Long.MIN_VALUE;
		    if(sum.get(i) < 0){
		        for(int j = 0; j < list.size(); j++){
		            long[] array = new long[min(list.size(), k)];
		            array[0] = list.get(j);
		            long tempA = array[0];
		            for(int K = 1; K < min(list.size(), k); K++){
		                array[K] = array[K-1] + list.get((j+K)%list.size());
		                tempA = max(tempA, array[K]);
		            }
		            temp = max(temp, tempA);
		        }
		    }else{
		        int cnt = k/list.size();
		        int tempk = k%list.size();
		        if(tempk == 0){
		            cnt = max(0, cnt-1);
		            tempk = list.size();
		        }
		        for(int j = 0; j < list.size(); j++){
		            long[] array = new long[min(list.size(), tempk)];
		            array[0] = list.get(j);
		            long tempA = array[0];
		            for(int K = 1; K < min(list.size(), tempk); K++){
		                array[K] = array[K-1] + list.get((j+K)%list.size());
		                tempA = max(tempA, array[K]);
		            }
		            temp = max(temp, tempA + sum.get(i)*cnt);
		        }
		    }
		    //System.out.println("i:" + i + " " + temp);
		    result = max(result, temp);
		}
		
		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}


Measured memory_bytes: 45324
while true do
  n = gets
  break if n == nil
  count = 0
  10.times do |i|
    10.times do |j|
      10.times do |k|
        10.times do |l|
          count += 1 if i+j+k+l == n.to_i
        end
      end
    end
  end

  puts count
end

Measured memory_bytes: 6092
#include <iostream>
using namespace std;
// エラトステネスのふるい
int main() {
  int n, prime[1000000];
  while (cin >> n) {
    for (int i = 0; i <= n; i++) {
      prime[i] = 0;
    }
    prime[0] = 1;
    prime[1] = 1;
    
    int count = 0;
    for (int i = 0; i <= n; i++) {
      if (prime[i] == 0) {
	count++;
	for (int j = i; j <= n; j += i) {
	  prime[j] = 1;
	}
      }
    }
    cout << count << endl;
  }
  return 0;
}


Measured memory_bytes: 6904
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <math.h>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
#include <sstream>
#include <stack>
#include <deque>
#include <memory.h>
#include <cassert>
#include <ctime>
#include <climits>
#include <list>
#include <time.h>
#include <unordered_map>
#include <bitset>
#include <exception>

using namespace std;


int main(){
  int n;
  cin >> n;
  int arr[n];
  int count = 1;
  int currMax;
  cin >> currMax;
  int temp;
  
  for(int i = 0; i < n-1; i++){
    cin >> temp;
    if (temp >= currMax){
      count++;
      currMax = temp;
    }
  }
  cout << count <<endl;
  
  
  
}


Measured memory_bytes: 256
from math import sqrt
N,D=map(int,input().split())
X=[list(map(int,input().split())) for _ in range(N)]
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    s = 0
    for k in range(D):
      s += (X[i][k] - X[j][k])**2
    r = sqrt(s)
    if r == int(r):
      ans+=1

print(ans)

Measured memory_bytes: 3064
#include <iostream>

using namespace std;

char table[1010][1010];
int sum[3][1010][1010];

int main(void){
	int m,n,q;
	cin >> m >> n >> q;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			cin >> table[i][j];

	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++){
			if(table[i][j]=='J')
				sum[0][i][j]++;
			else if(table[i][j]=='O')
				sum[1][i][j]++;
			else
				sum[2][i][j]++;
			for(int k=0;k<3;k++)
				sum[k][i][j]+=sum[k][i-1][j]+sum[k][i][j-1]-sum[k][i-1][j-1];
		}

	for(int i=0;i<q;i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		for(int j=0;j<3;j++){
			cout << (j?" ":"") << (sum[j][c][d]-sum[j][a-1][d]-sum[j][c][b-1]+sum[j][a-1][b-1]);
		}
		cout << endl;
	}	
	return 0;
}

Measured memory_bytes: 14096
function A168(_input) {
    var lines = _input.split("\n");
    var first = parseInt(lines.shift().slice(-1), 10);
  
    if ([2,4,5,7,9].indexOf(first) !== -1) {
        console.log('hon');
    } else if ([0,1,6,8].indexOf(first) !== -1) {
        console.log('pon');
    } else if ([3].indexOf(first) !== -1) {
        console.log('bon');
    }
}
A168(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29624
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int main(void)
{
    int i,j;
    long long int a,b,k;
    cin >> a >> b >> k;
    if(a + k > b - k)
    {
        for(i = a;i <= b;i++)
        {
            cout << i << endl;
        }
    }
    else
    {
        for(i = a;i < a + k;i++)
        {
            cout << i << endl;
        }
        for(j = b - k + 1;j <= b;j++)
        {
            cout << j << endl;
        }
    }
    return 0;
}

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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define mp make_pair
#define ll long long
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define pdd pair< double, double >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 2097162
#define inf 1e9
#define MOD 1000000007

ll ret(ll l, ll r)
{

    return ((l%2019)*(r%2019))%2019;
}

int main()
{

    ll l, r, ans = inf;
    cin >> l >> r;
    if(r-l >= 2018) cout << 0;
    else
    {

        l%=2019;
        r%=2019;
        if(r < l) r+=2019;
        for(ll i = l; i <= r; i++)
            for(ll j = i+1; j <= r; j++)
             ans = min(ans, ret(i,j));
        cout << ans;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ll q, h, s, d, n;
    cin >> q >> h >> s >> d >> n;

    ll q2 = q * 8;
    ll h2 = h * 4;
    ll s2 = s * 2;

    ll x = min(min(q2, h2), min(s2, d));
    ll ans = (n/2) * x;

    if(n%2 == 0) cout << ans << endl;
    else
    {
        ll q1 = q2 / 2;
        ll h1 = h2 / 2;
        ll y = min(q1, min(h1, s));
        cout << ans + y << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N; cin >> N;
  vector<double> A(N);
  vector<double> B(N);
  double C; C=0;
  
  for(int i=0; i<N; i++){
    cin >> A[i];
    B[i] = 1/A[i];
    C += B[i];
  }
  
    cout << 1/C << endl;
}

Measured memory_bytes: 256
l = ["000", "001", "010", "011", "100", "101", "110", "111"]
def f(x):
  return 1-2*int(x)

n,m = map(int,input().split())
a = []
for _ in [0]*n:
  a += [list(map(int,input().split()))]
s = 0
for t in l:
  b = [f(t[0])*p[0]+f(t[1])*p[1]+f(t[2])*p[2] for p in a]
  b.sort()
  b.reverse()
  s = max(s,sum(b[:m]))
print(s)

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

int MaxEatableCockie(int A, int B, int C){
  if(C>A+B+1){
    return A+2*B+1;
  } else {
    return B+C;
  }
}

int main(){
  int A,B,C;
  cin >> A >> B >> C;
  cout << MaxEatableCockie(A, B, C) << endl;
}


Measured memory_bytes: 256
n=int(input())
w=list(map(int,input().split()))
s1,s2,ans=0,sum(w),1000
for t in range(n):
    s1+=w[t]
    s2-=w[t]
    if abs(s1-s2)<ans:
        ans=abs(s1-s2)
        
print(ans)

Measured memory_bytes: 9180
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
f=[]
for x in l:
	f.append(x[0]==x[1])
l=f.copy()
i=0
while i<n:
	j=1
	while i+j<n and l[i+j]==l[i] and l[i]:
		j+=1 
	if j>2:
		print('Yes')
		break	
	i+=j
else:
	print('No')
	

Measured memory_bytes: 9184
n, m = map(int, input().split())
sum = 0

for i in range(m, n + 2):
    min = (i - 1) * i / 2
    max = (2 * n - i + 1) * i / 2
    sum += max - min + 1
print(int(sum % (10 ** 9 + 7)))


Measured memory_bytes: 9176
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
/*--Input//////////////////////////////////////////////////*/
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
#define SS(T, ...)      T __VA_ARGS__; IN(__VA_ARGS__);
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
/*--Output/////////////////////////////////////////////////*/
inline int p(void){cout << endl; return 0;}
template<class Head> int p(Head&& head){cout << head;p();return 0;} template<class Head,class... Tail> int p(Head&& head,Tail&&... tail){cout<<head<<" ";p(forward<Tail>(tail)...);return 0;}
struct ProconInit {
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(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; }
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second < b.second; }


int main() {
    SS(long double,l)
    p(l/3*l/3*l/3);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long int
#define INF INT_MAX
#define mod 1000000007
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
int main()
{
    chutiyaap;
    int n,m;cin>>n>>m;
    int h[n+10];for(int i=1;i<=n;i++)cin>>h[i];
    vector<int>v[n+1];
    for(int i=0;i<m;i++)
    {
    	int x,y;cin>>x>>y;
    	v[x].pb(y);
    	v[y].pb(x);
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
    	int cnt=0,chk=h[i],sz=v[i].size();
    	for(int j=0;j<sz;j++)
    	{
    		if(h[v[i][j]]<chk)cnt++;
    	}
    	if((cnt==sz)||(sz==0))res++;
    }
    cout<<res;
}


Measured memory_bytes: 9136
A = [list(map(int, input().split())) for _ in range(3)]

N = int(input())

for _ in range(N):
    b = int(input())

    for i, row in enumerate(A):
        for j, a in enumerate(row):
            if a == b:
                A[i][j] = -1

for i in range(3):
    f = True
    for j in range(3):
        f &= A[i][j] == -1

    if f:
        print('Yes')
        exit()

for i in range(3):
    f = True
    for j in range(3):
        f &= A[j][i] == -1

    if f:
        print('Yes')
        exit()

f = True
for i in range(3):
    f &= A[i][i] == -1

if f:
    print('Yes')
    exit()

f = True
for i in range(3):
    f &= A[2-i][i] == -1

if f:
    print('Yes')
    exit()


print('No')

Measured memory_bytes: 3064
#include <cstdio> 
#include <cstring>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
const int MAXN=2*1e5+10;

LL a[MAXN];
LL ans1,ans2,ans3,ans4;
LL Min=INF;
int n;

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
		cin>>a[i],a[i]=a[i-1]+a[i];
	int l=1,r=3;
	for (int i=2;i<=n-2;i++)
	{
		while (l<i && abs(a[l]-abs(a[i]-a[l]))>=abs(a[l+1]-abs(a[i]-a[l+1]))) l++; 
		while (r<n && abs(a[r]-a[i]-abs(a[n]-a[r]))>=abs(a[r+1]-a[i]-abs(a[n]-a[r+1]))) r++;
		ans1=a[l];
		ans2=a[i]-a[l];
		ans3=a[r]-a[i];
		ans4=a[n]-a[r];
		Min=min(Min,max(ans1,max(ans2,max(ans3,ans4)))-min(ans1,min(ans2,min(ans3,ans4))));
	}
	cout<<Min<<endl;
	return 0;
} 

Measured memory_bytes: 1792
#include<stdio.h>

int d[20],i,a,b;
double x,y;

int main(){
	while(scanf("%d",&d[0])!=EOF){
		x=d[0];y=0.0;
		for(i=1;i<10;i++)scanf(",%d",&d[i]),x+=d[i];
		scanf(",%d,%d",&a,&b);
		x=x*a/(a+b);i=0;
		while(y<x)y+=d[i],i++;
		printf("%d\n",i);
	}
	return 0;
}

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


int main() {
    int N;
    cin >> N;
    vector<int> d(N);
    rep(i,N) cin >> d.at(i);
    sort(d.begin(), d.end());
    cout << d.at(N / 2) - d.at(N / 2 - 1) << endl;
}


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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define fi first
#define se second
#define setpre(x) cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ cout << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 400005;

/* ...o(^-^)o... */
lint c[26];
int main(){
    string s; cin >> s; lint ans = s.size()*(s.size()-1)/2 + 1;
    rep(i, s.size()) c[s[i]-'a']++;
    rep(i, 26) ans -= c[i]*(c[i]-1)/2;
    out(ans);
}

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

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;

    int da,dc;
    da=(a+d-1)/d;
    dc=(c+b-1)/b;
    if(da<dc)
    {
        cout<<"No";
    }
    else{
        cout<<"Yes";
    }






}


Measured memory_bytes: 3624
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<functional>
#include<cstring>

using namespace std;

int main()
{
	int a, b, m;

	scanf("%d %d %d", &a, &b, &m);

	vector<int> ref, mic;

	ref.push_back(0);
	mic.push_back(0);

	int temp = 100001;
	int lmin = 0;

	for (int i = 0; i < a; i++)
	{
		int input;

		scanf("%d", &input);

		ref.push_back(input);

		if (input < temp)
		{
			temp = input;
		}
	}

	lmin += temp;

	temp = 100001;

	for (int i = 0; i < b; i++)
	{
		int input;

		scanf("%d", &input);

		mic.push_back(input);

		if (input < temp)
		{
			temp = input;
		}
	}

	lmin += temp;

	for (int i = 0; i < m; i++)
	{
		int ai, bi, ci;

		scanf("%d %d %d", &ai, &bi, &ci);

		if (ref[ai] + mic[bi] - ci < lmin)
		{
			lmin = ref[ai] + mic[bi] - ci;
		}
	}

	printf("%d\n", lmin);

	return 0;
}

Measured memory_bytes: 1400
#include <stdio.h>

static int c, ks[10];

void rec(int n, int s) {
  if (n == 0) {
    if (s == 0)
      c++;
    return;
  }
  int j = 9;
  while (ks[j])
    j--;
  if ((j * (n * (n + 1) / 2)) < s)
    return;
  for (j = s / n < j ? s / n : j; j >= 0; j--)
    if (!ks[j]) {
      ks[j] = 1;
      rec(n - 1, s - n * j);
      ks[j] = 0;
    }
}

int main() {
  int n, s;
  while (scanf("%d%d", &n, &s) == 2) {
    c = 0;
    rec(n, s);
    printf("%d\n", c);
  }
  return 0;
}

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

class Program
{
    static void Main()
    {
        Scanner cin = new Scanner();
        int N = cin.Int();
        long[] a = cin.ArrayLong(N);

        long sum = 0;
        foreach(var x in a)
        {
            sum += x;
        }

        long ans = int.MaxValue, tmp = 0;
        for(int i = 0; i < N - 1; i++)
        {
            tmp += a[i];
            long t = Math.Abs(tmp - (sum - tmp));
            ans = Math.Min(ans, t);
        }

        Console.WriteLine(ans);
        Console.ReadLine();
    }

}

class Scanner //標準入力
{
    string[] s;
    int i;

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

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

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

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

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

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = Long() + add;
        }
        return Array;
    }

    public double Double()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = Double() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 29916
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define P pair<int, int>
#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define LAST(x) (x)[(x).size() - 1]
#define GI(name) \
  int(name);     \
  scanf("%d", &(name))
#define GI2(name1, name2) \
  int(name1), (name2);    \
  scanf("%d %d", &(name1), &(name2))
#define GI3(name1, name2, name3) \
  int(name1), (name2), (name3);  \
  scanf("%d %d %d", &(name1), &(name2), &(name3))
#define GVI(name, size)    \
  vector<int>(name)(size); \
  FOR(i, (size)) scanf("%d", &(name)[i])
#define GS(name) \
  string(name);  \
  cin >> (name);
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  FOR(i, v.size() - 1) { ret += to_string(v[i]) + ","; }
  if (v.size() > 0) {
    ret += to_string(LAST(v));
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

int main() {
  GI(N);
  vector<vector<P>> G(N, vector<P>());
  FOR(i, N) {
    GI3(a, b, v);
    G[a - 1].push_back(P(b - 1, v));
    G[b - 1].push_back(P(a - 1, v));
  }
  stack<int> s;
  vector<bool> visited(N);
  visited[0] = 1;
  s.push(0);
  vector<int> colors(N);
  while (!s.empty()) {
    int v = s.top();
    s.pop();
    for (P p : G[v]) {
      if (!visited[p.first]) {
        visited[p.first] = 1;
        s.push(p.first);
        if (p.second % 2 == 0) {
          colors[p.first] = colors[v];
        } else {
          colors[p.first] = !colors[v];
        }
      }
    }
  }
  FOR(i, N) { print(colors[i]); }
  return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)

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

const int MAX = 1e5;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int N;

int main(){
    cin >> N;

    printf("%.15f\n", (double)((N + 1) / 2) / N);
}

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

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

typedef pair<int, int> P;

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( a > b ) { a = b; return 1; } return 0; }

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

signed main(){
  int N, sum = 0; cin >> N;
  vector<int> a( N );
  REP( i, N ) {
    cin >> a[i];
    sum += a[i];
  }

  int x = sum;
  for( int i = 1; i < N - 1; i += 2 ){
    x -= 2 * a[i];
  }

  cout << x;
  REP( i, N - 1 ){
    x = 2 * a[i] - x;
    cout << " " << x;
  }
  cout << endl;
  
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100000];
long long b[100000];
long long d[100000];
int main(){
	cin>>n;
	for(int i=0;i<n;i++)	cin>>a[i];
	for(int i=0;i<n;i++)	cin>>b[i];
	long long k=0;
	for(int i=0;i<n;i++)	k+=b[i]-a[i];
	long long two=0;
	for(int i=0;i<n;i++)
	{
		long long d=b[i]-a[i];
		if(d>0)	two+=(d+1)/2;
	}
	if(two>k) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
}

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

//足場nまでのコストの最小値
int minC[100000+1];
//minC[n] = minC[n - 1] + cost(n-1,1) or minC[n - 2] + cost(n - 2,n)

//足場の高さ
int height[100000+1];

int cost(int x,int y)
{
    if(height[x]>height[y]) return height[x] - height[y];
    else return height[y] - height[x];
}

int main()
{
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> height[i];
    if(N == 2) cout << cost(1 - 1,2 - 1);
    else{
        minC[1 - 1] = 0;
        minC[2 - 1] = cost(1 - 1,2 - 1);
        for(int i = 3 - 1; i <= N - 1; i++){
            minC[i] = min(minC[i - 1] + cost(i - 1,i) , minC[i - 2] + cost(i - 2,i)); 
        }
        cout << minC[N - 1];
    }
    return 0;
}
    
    


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

int main() {
 
  int n;
  int k=0;
  cin>>n;
  vector<int> a(n);
  int b;
  int c;
  for(int i=0;i<n;i++){cin>>b; a.at(i)=b; k=k ^ b;}
for(int i=0;i<n-1;i++){c=k ^ (a.at(i));cout<<c<<" ";}
  c=k ^ (a.at(n-1));
  cout<<c;
  
}

Measured memory_bytes: 4044
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

mod = 10 ** 9 + 7


def dfs(v, bf):
    if bf == -1:
        can_use = k - 1
    else:
        can_use = k - 2

    if k <= len(es[v]):
        return 0
    else:
        case_num = 1
        for nv in es[v]:
            if nv == bf: continue
            case_num *= can_use
            case_num %= mod
            can_use -= 1

        for nv in es[v]:
            if nv == bf: continue
            case_num *= dfs(nv, v)
            case_num %= mod

    return case_num


n, k = map(int, input().split())

es = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    es[b].append(a)

ans = k * dfs(0, -1) % mod
print(ans)


Measured memory_bytes: 87344
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	int N; cin >> N;
	vector<int> a(N), b(N);
	rep(i, N) cin >> a[i];
	rep(i, N) cin >> b[i];
	vector<i_i> p;
	rep(i, N) p.pb(i_i(a[i], 0));
	rep(i, N) p.pb(i_i(b[i], 1));
	sort(p.begin(), p.end());
	vector<int> num(2);
	ll ans = 1;
	for (i_i z: p) {
		int t = z.second;
		if (num[!t]) {
			ans = ans * num[!t] % MOD;
			num[!t]--;
		}
		else num[t]++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define int long long
//#define _GLIBCXX_DEBUG

vector<int> comb(int N, int mod) {
  bitset<30> modbit = mod-2;
  vector<int> comb(N+1, 1);
  rep(i, N) {
    comb[i+1] = (comb[i]*(N-1-i))%mod;
    int x = i+1;
    rep(j, 30) {
      if(j > 0) x *= x;
      x %= mod;
      if(modbit.test(j)) {
        comb[i+1] *= x;
        comb[i+1] %= mod;
      }
    }
  }
  return comb;
}

signed main() {
  int N, M, K; cin >> N >> M >> K;
  const int mod = 998244353;
  M %= mod;
  /*vector<int> com(K+1, 1);
  rep(i, K) {
    com[i+1] = (com[i]*(N-1-i))%mod;
    int x = i+1;
    rep(j, 30) {
      if(j > 0) x *= x;
      x %= mod;
      if(j != 26 && j != 23) {
        com[i+1] *= x;
        com[i+1] %= mod;
      }
    }
  }*/
  vector<int> com = comb(N, mod);
  //cout << com[0] << endl << com[1] << endl << com[2] << endl;

  vector<int> paint(N+1, M);
  rep(i, N-1) paint[i+2] = (paint[i+1]*(M-1))%mod;
  
 
  int ans = 0;
  rep(i, K+1) {
    ans += com[i]*paint[N-i];
    ans %= mod;
  }

  cout << ans << endl;
}

Measured memory_bytes: 6428
S = input()

chrs = set() #先頭、3~last-1のCを覗いた文字の集合

if S[0:1] != 'A':
  print('WA')
  exit()

ccnt = 0 #3~last-1までのCの数
for c in S[2:len(S)-1]:
  if c == 'C': ccnt += 1

if ccnt != 1:
  print('WA')
  exit()
  
#残りの文字を集合に入れる
chrs.add(S[1:2]) #2文字目を追加
for c in S[2:len(S)-1]: #3~last-1を追加
  chrs.add(c)
chrs.remove('C') #正しいCが入っちゃったのでそれは除く
chrs.add(S[len(S)-1:len(S)])

#集合に大文字があればWA
for ng in range(ord('A'), ord('Z')+1, 1):
  if chr(ng) in chrs:
    print('WA')
    exit()
    
#AC
print('AC')

Measured memory_bytes: 3064
N,K=map(int,input().split())
li=list(map(int,input().split()))

N_keta=list(map(int,str(N)))

for n in range(100000):
  count=0
  for k in range(len(N_keta)):
    if N_keta[k] in li:
      count=1
      break
    
  if count==0:
    print(N)
    break
  else:
    N+=1
    N_keta=list(map(int,str(N)))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if (s == "SUN")
    {
        cout << 7 << endl;
    }else if(s == "MON"){
        cout << 6 << endl;
    }else if(s == "TUE"){
        cout << 5 << endl;
    }else if(s == "WED"){
        cout << 4 << endl;
    }else if(s == "THU"){
        cout << 3 << endl;
    }else if(s == "FRI"){
        cout << 2 << endl;
    }else{
        cout << 1 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
	int n, k;
	cin >> n >> k;
	int arr[n];
	for (int i = 0; i < n; i++) cin >> arr[i];
	if (n == 1) {
		cout << 0;
	} else if (n == 2){
		cout << (arr[1] - arr[0]);
	} else {
		int DP[n];
		DP[0] = 0; DP[1] = abs(arr[1] - arr[0]);
		for (int i = 2; i < n; i++){
			vector <int> b;
			for (int j = 1; j <= k; j++){
				if ((i - j) < 0) break;
				b.push_back(DP[i-j] + abs(arr[i] - arr[i-j]));
			}
			DP[i] = (*min_element(b.begin(), b.end()));
		}
		cout << endl;
		cout << DP[n-1];
	}
	return 0;
}

Measured memory_bytes: 4352
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef pair< ll, int > pli;
typedef pair< int, ll > pil;

ll ceil(ll x, ll y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y){
  return x / gcd(x, y) * y;
}

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

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

  ll mi = a[0];
  for(int i = 1; i < 5; i++){
    mi = min(mi, a[i]);
  }

  ll ans = ceil(n, mi) + 4;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
n = gets.chomp.to_i
A = gets.chomp.split.map(&:to_i).sort.reverse

ans = A[0]
n -= 2
sho = n / 2
amari = n % 2

(1..sho).each do |i|
  ans += (A[i] * 2)
end

if amari == 1
  ans += A[sho + 1]
end

puts ans

Measured memory_bytes: 33228
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n;
	cin >> n;
	
	while(n-- > 0){
	
	double x1, y1, x2, y2, x3, y3;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
	
	double a = 2 * (x2 - x1);
	double b = 2 * (y2 - y1);
	double c = x1 * x1 - x2 * x2 + y1 * y1 - y2 * y2;
	double d = 2 * (x3 - x2);
	double e = 2 * (y3 - y2);
	double f = x2 * x2 - x3 * x3 + y2 * y2 - y3 * y3;
		
	double cx = (b * f - c * e)/(a * e - d * b);
	double cy = (a * f - c * d)/(b * d - a * e);
		
	double r = sqrt((x1 - cx)*(x1 - cx) + (y1 - cy)*(y1 - cy));
	
	cout << fixed << setprecision(3) << cx << " " << cy << " " << r << endl;
	
	}
	
	return 0;
}

Measured memory_bytes: 1304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<ll>>;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define MOD 1000000007
#define INF 1000000
#define PI 3.14159265358979323846264338327950L
#define MAX_N 200010
#define lb lower_bound 

int main()
{
  ll N;cin>>N;
  ll ans=1;
  vector<ll> A(N);
  for (ll i=0;i<N;i++){
    cin>>A[i];
    if (A[i]==0){
      cout<<0<<endl;
      return (0);
    }
  }
  
  bool f = false;
  ll lim = pow(10,18);
  for (ll i=0;i<N;i++){
    if (lim/A[i]<ans && A[i]!=0)
    {
      f = true;
      break;
    }
    ans *= A[i];
  }
  if (f)
    cout<<-1<<endl;
  else
    cout<<ans<<endl;
}

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

int n;
string s, t, ans;

string p(const string &s, const string &t) {
	string res;
	int l1 = s.length()-1, l2 = t.length()-1;
	int L = max(l1, l2);
	int pre = 0;
	for (int i = 0; i <= L; ++i) {
		int sum = pre;
		sum += (l1>=0 ? s[l1--]-'0' : 0);
		sum += (l2>=0 ? t[l2--]-'0' : 0);
		pre = sum/10;	// 繰り上げ分
		sum -= pre*10;
		res += '0' + sum;
	}
	if (pre) res += '0' + pre;
	reverse(res.begin(), res.end());
	return res;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n;
	rep(T,n) {
		cin >> s >> t;
		ans = p(s, t);
		if (ans.length() > 80) cout << "overflow" << endl;
		else cout << ans << endl;
	}
}


Measured memory_bytes: 3112
/*	
*  Sachin Mittal
*/
#include<bits/stdc++.h>
#define int long long
#define M 998244353
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define mem0(dp) memset(dp,0,sizeof(dp))
#define mem1(dp) memset(dp,-1,sizeof(dp))
#define pb push_back
#define sz(s) (int)(s.size())
using namespace std;
int32_t main(){
ios
int t=1;
//cin>>t;
while(t--)
{
	int a,b,c;cin>>a>>b>>c;
	cout<<c<<" "<<a<<" "<<b;
}
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>
#include <queue>

#define MAX 21
#define ll long long int
using namespace std;

string s; //??\?????¨

int ctoi(char c) {
	switch (c) {
	case '0': return 0;
	case '1': return 1;
	case '2': return 2;
	case '3': return 3;
	case '4': return 4;
	case '5': return 5;
	case '6': return 6;
	case '7': return 7;
	case '8': return 8;
	case '9': return 9;
	default: return -1;
	}
}

int ele_dis(int st, int en) //start ?????? end ?????§???????\¨??°
{
	int i, j = 0;
	vector <int> hyou;
	int temp = 0;
	int k = 1;
	int n;
	int res = 0;

	int l, r; //left, right


	 //?????????????????????????????????????¢??????????
	if (s[st + 1] == '[') {
		int count = 0;
		l = st + 1;

		for (i = st + 1; i < en; i++) {
			if (s[i] == '[') {
				count++;
			}
			else if (s[i] == ']') {
				count--;
			}

			if (count == 0) {
				r = i;
				hyou.push_back(ele_dis(l, r));
				l = i + 1; //?¬?????????????
			}

		}

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

		n = (hyou.size() + 1) / 2;

		for (i = 0; i < n; i++) {
			res = res + hyou[i];
		}

		return (res);

	}
	else {
		// ??????????????????????????´???

		for (i = en - 1; i > st; i--) {


			temp = temp + k * ctoi(s[i]);
			k = k * 10;
		}


		return (temp / 2 + 1);

	}



}


int solve(void)
{
	int ans;

	ans = ele_dis(0, s.length() - 1); //????????????????????????

	return (ans);

}




int main(void)
{
	int n;
	int i;
	int ans;


	cin >> n;


	for (i = 0; i < n; i++) {
		cin >> s;

		ans = solve();


		cout << ans << endl;
		s.clear();
	}



	return (0);
}

Measured memory_bytes: 3192
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 1e5+5,mod = 1e9+7;
it add(int x,int y){ return x+y>=mod?x+y-mod:x+y; }
it mul(int x,int y){ return 1ll*x*y%mod; }
il inc(int &x,int y){ x=add(x,y); }
int n,m,id,u,v,ans,S,f[N],g[N],cnt[N],bas[N];
int main(){
//	freopen("winner.in","r",stdin);
//	freopen("winner.out","w",stdout);
	read(n),read(m),S=1<<n,bas[0]=1;
	for(ri i=1;i<=m;++i){
		read(u),read(v),bas[i]=mul(bas[i-1],2);
		for(ri T=0;T<S;++T) if((T&(1<<(u-1)))&&(T&(1<<(v-1)))) ++cnt[T];
	}
	ans=bas[m],f[1]=1,g[2]=1;
	for(ri T=2;T<S;++T) if(T&1){
		f[T]=bas[cnt[T]];
		for(ri t=(T-1)&T;t;t=(t-1)&T)
			inc(f[T],mod-mul(f[t],bas[cnt[T^t]]));
	}
	for(ri T=3;T<S;++T) if(T&2){
		g[T]=bas[cnt[T]];
		for(ri t=(T-1)&T;t;t=(t-1)&T)
			inc(g[T],mod-mul(g[t],bas[cnt[T^t]]));
	}
	for(ri T=0;T<S;++T){
		for(ri t=T;t;t=(t-1)&T) if(t&2){
			int s=(S-1)^T;
			if((s&1)&&(cnt[s|t]==cnt[s]+cnt[t]))
				inc(ans,mod-mul(mul(f[s],g[t]),bas[cnt[(S-1)^(s|t)]]));
		}
	}
	print(ans);
	return 0;
}

Measured memory_bytes: 640