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

int isprime(int n){
    int i;
	for(i = 2; i * i <= n; i++){
        	if(n % i == 0) return 0;
    	}
    return 1;
}

int main(){
    int i,n;
    while(scanf("%d", &n) != EOF){
        for(i = n; i >= 5; i--){
            if(isprime(i) && isprime(i-2)) {
                printf("%d %d\n", i-2, i);
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1740
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <math.h>
#include <complex>
#include <cassert>
#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define repd(i,a,b) for(int i = (a); i > (b); i--)
using namespace std;
typedef long long int ll;
typedef complex<double> com;
typedef pair<int, int> P;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const ll INF = 4e18;



int main() {
	int n; cin >> n;
	vector<ll> a(3*n),l,r;
	rep(i, 0, 3 * n) cin >> a[i];
	priority_queue<ll,vector<ll>,greater<ll>> pq1;
	ll sum = 0;
	rep(i, 0, n) {
		pq1.push(a[i]);
		sum += a[i];
	}l.push_back(sum);
	rep(i, n, 2 * n) {
		pq1.push(a[i]);
		sum += a[i];
		sum -= pq1.top(); pq1.pop();
		l.push_back(sum);
	}
	priority_queue<ll> pq2; sum = 0;
	rep(i, 2 * n, 3 * n) {
		pq2.push(a[i]); sum += a[i];
	}r.push_back(sum);
	repd(i,2*n-1,n-1){
		pq2.push(a[i]);
		sum += a[i];
		sum -= pq2.top(); pq2.pop();
		r.push_back(sum);
	}
	reverse(r.begin(), r.end());
	ll ans = -INF;
	rep(i, 0, l.size()) {
		ans = max(ans, l[i] - r[i]);
	}
	printf("%lld", ans);
	return 0;
}


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


int main()
{
	//真理値表
	char getminus[3], getmulti[3][3], getplus[3][3];
	getminus[0] = '2';
	getminus[1] = '1';
	getminus[2] = '0';
	for (int i = 0; i < 3; i++){
		for (int j = 0; j < 3; j++){
			if (i == 0 || j == 0){
				getmulti[i][j] = '0';
			}
			else if (i == 2 && j == 2){
				getmulti[i][j] = '2';
			}
			else
				getmulti[i][j] = '1';
		}
	}
	for (int i = 0; i < 3; i++){
		for (int j = 0; j < 3; j++){
			if (i == 2 || j == 2){
				getplus[i][j] = '2';
			}
			else if (i == 0 && j == 0){
				getplus[i][j] = '0';
			}
			else
				getplus[i][j] = '1';
		}
	}

	string s, inits;
	while (cin >> inits, inits[0] != '.'){
		int counter = 0;
		for (char p = '0'; p < '3'; p++){
			for (char q = '0'; q < '3'; q++){
				for (char r = '0'; r < '3'; r++){
					s = inits;
					//代入
					for (int i = 0; i < (signed)s.length(); i++){
						if (s[i] == 'P'){
							s[i] = p;
						}
						else if (s[i] == 'Q'){
							s[i] = q;
						}
						else if (s[i] == 'R'){
							s[i] = r;
						}
					}

					while (s.length()>1){

						// "-"を探索し，書き換える
						for (int i = 0; i < (signed)s.length() - 1; i++){
							if (s[i] == '-'&& s[i + 1] != '-' && s[i + 1] != '('){
								s[i] = getminus[(int)s[i + 1] - '0'];
								s.erase(s.begin() + i + 1);
								break;
							}
						}
						if (s.length() == 1){
							break;
						}

						//"*"を探索し，書き換える
						for (int i = 0; i < (signed)s.length() - 4; i++){
							if (s[i] == '('&& s[i + 2] == '*' && s[i + 4] == ')'){
								s[i] = getmulti[(int)s[i + 1] - '0'][(int)s[i + 3] - '0'];
								s.erase(i + 1, 4);
								break;
							}
						}
						if (s.length() == 1){
							break;
						}

						//"+"を探索し，書き換える
						for (int i = 0; i < (signed)s.length() - 4; i++){
							if (s[i] == '('&& s[i + 2] == '+' && s[i + 4] == ')'){
								s[i] = getplus[(int)s[i + 1] - '0'][(int)s[i + 3] - '0'];
								s.erase(i + 1, 4);
								break;
							}
						}

					}
					if (s[0] == '2'){
						counter++;
					}
				}
			}
		}
		cout << counter++ << endl;
	}
	return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int main() {
	int n, w[101], left=0, right=0, mn=10001;
	
	cin>>n; for(int i=0;i<n;i++) cin>>w[i];
	
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			left+=w[j];
		}
		for(int k=i+1;k<n;k++){
			right+=w[k];
		}
		if(mn>abs(left-right)) mn=abs(left-right);
		left=0; right=0;
	}
	
	cout<<mn;
	
	return 0;
}

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

using namespace std;

#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) FOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;

const double eps = 1e-10;
const int MOD = 1000000007;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, s.size()) {
    cout << s[i] << " ";
  }
  cout << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  while(1) {
    string s; getline(cin, s);
    if(s == ".") break;
    stack<char> st;
    bool balance = true;
    REP(i, SZ(s)) {
      if(s[i] == '(' || s[i] == '[') st.push(s[i]);
      else if(s[i] == ')') {
        if(!st.empty() && st.top() == '(') st.pop();
        else balance = false;
      } else if(s[i] == ']') {
        if(!st.empty() && st.top() == '[') st.pop();
        else balance = false;
      }
    }
    if(balance && st.empty()) cout << "yes" << endl;
    else cout << "no" << endl;
  }
}



Measured memory_bytes: 3140
#include <stdio.h>

int main(void)
{
	
	int a, b, c;
	
	scanf("%d %d %d", &a, &b, &c);
	
	if (a < b && b < c){
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	
	
	return (0);
}

Measured memory_bytes: 580
N, X = map(int, input().split())
a = [1]
p = [1]
for i in range(N):
    a.append(2*a[-1] + 3)
    p.append(2*p[-1] + 1)
def f(N, X):
    if N == 0:
        if X <= 0:
            return 0
        else:
            return 1
    elif X <= 1 + a[N-1]:
        return f(N-1, X-1)
    else:
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])
print(f(N, X))

Measured memory_bytes: 38384
package main
import (
    "fmt"
    "bufio"
    "os"
    "strconv"
    "strings"
)
var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)
func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
func scanf(f string, a ...interface{}) { fmt.Fscanf(reader, f, a...) }
func dig(s string) int64 {
    var res int64 = 0
    for i := 0; i < len(s); i++ {
        res += int64(s[i] - '0')
    }
    return res
}
func main() {
    defer writer.Flush()
    var n int
    scanf("%d\n",&n)
    var a int64 = 1
    for i := 0; i < n; i++ {
        printf("%d\n", a)
        var b = a+1
        // var sa = strconv.FormatInt(a,10)
        var sb = strconv.FormatInt(b,10)
        var na,da int64 = -1,-1;
        for j := 0; j <= len(sb); j++ {
            var st = sb[:j] + strings.Repeat("9", len(sb) - j)
            var t, _ = strconv.ParseInt(st, 10, 64)
            // printf("%s st=%d t=%d na=%d, da=%d\n",st,t,dig(st),na,da)
            // printf("a*dig(st)=%d t*da=%d\n",a*dig(st),t*da)
            if na == -1 || na*dig(st) >= t*da{
                na=t
                da=dig(st)
            }
        }
        a=na
    }
}

Measured memory_bytes: 2040
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();

		int frag = 0;
		if (S.charAt(0) == 'A') {
			for (int i = 2; i < S.length() - 1; i++) {
				if (S.charAt(i) == 'C') {
					frag = 1;
					break;
				}
			}
		}
		int cnt = 0;
		for (int i = 0; i < S.length(); i++) {
			if (Character.isUpperCase(S.charAt(i)))
				cnt++;
		}
		if (cnt != 2)
			frag = 0;

		if (frag == 1) {
			System.out.println("AC");
		} else {
			System.out.println("WA");
		}
		sc.close();
	}
}

Measured memory_bytes: 23636
N = int(input())
W = [input() for _ in range(N)]

result = 'Yes'
if len(set(W)) != len(W):
    result = 'No'
else:    
    for i in range(1,N):
        if W[i][0] != W[i-1][-1]:
            result = 'No'
            break 
print(result)

Measured memory_bytes: 9160
//BISMILLAHIR RAHMANIR RAHIM
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <list>
#define cos(a) cos(a*pi/180)
#define sin(a) sin(a*pi/180)
#define tan(a) tan(a*pi/180)
#define cosi(a) acos(a)/(pi/180)
#define sini(a) asin(a)/(pi/180)
#define tani(a) atan(a)/(pi/180)
#define mem(a, b) (memset(a, b, sizeof(a)))
#define read (freopen("input.txt", "r", stdin))
#define write (freopen("output.txt", "w", stdout))
#define fastIO (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0));
#define dis(x1, y1, x2, y2) ((x1-x2) * (x1-x2)) + ((y1-y2) * (y1-y2))
#define debug (printf("PINK FLOYD:)\n"))
#define iosflags (cout<<setiosflags(ios::fixed)<<setprecision(8))
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define PI acos(-1)
#define pi 3.1415926535897932384
#define INF 2147483647
#define EPS 1e-8
#define MOD 1000000007
#define MAX 100005
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
typedef vector<ii> vii;
typedef priority_queue<int,vector<int>,greater<int> > PQ;

const int inf = 1<<28;
int dirx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int diry[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int fx[] = { -2, -2, -1, -1,  1,  1,  2,  2 };
int fy[] = { -1,  1, -2,  2, -2,  2, -1,  1 };

int Set(int mask, int pos){return mask = mask | (1<<pos);}
bool check(int mask, int pos){return (bool)(mask & (1<<pos));}

int arr[MAX*2], tarr[MAX*2];

int main()
{
	fastIO;
    int n, sum = 0;
    vector<int> ans;
    cin>>n;

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

    for(int i = n; i >= 1; i--){
        int cs = 0;
        for(int j = i; j <= n; j += i){
            cs += tarr[j];
        }
        if(cs % 2 != arr[i]){
            tarr[i] = !arr[i];
        }
        if(tarr[i]){
            ans.pb(i);
        }
    }

    for(int i = 1; i <= n; i++){
        int cs = 0;
        for(int j = i; j <= n; j += i){
            cs += tarr[j];
        }
        if(cs % 2 != arr[i]){
            cout<<-1<<endl;
            return 0;
        }
    }

    cout<<ans.size()<<endl;
    for(int i = 0; i < ans.size(); i++){
        cout<<ans[i]<<" ";
    }
    if(ans.size())
        cout<<endl;

    return 0;
}


Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
const int N = 3000 + 5;
int n,t;
int vis[N];

int main()
{
	cin>>n>>t;
  	vector< pair<int, int> > data;
  	int a, b;
  	for (int i = 0; i < n; i++) {
    	cin >> a >> b;
    	data.push_back({a, b});
  	}
  	sort(data.begin(), data.end());
	int ans = 0;
  	for(int j=0; j<n; j++) {
    	for(int i=t-1; i>=0; i--) {
      		if((i+data[j].first) < t)
				vis[i+data[j].first] = max(vis[i+data[j].first], vis[i] + data[j].second);
      		ans = max(ans, vis[i] + data[j].second);
    	}
  	}
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.next().toLong()
    val a = sc.next().toLong()
    val b = sc.next().toLong()

    println(abc158b(n, a, b))
}

private fun abc158b(n: Long, a: Long, b: Long): Long {
    val ab = a + b
    if (ab == 0L) return 0L

    val roop = n / (a + b)
    var ans = a * roop

    if (n % (a + b) != 0L) {
        val last = n - (a + b) * roop
        if (a <= last) {
            ans += a
        } else {
            ans += last
        }
    }

    return ans
}

Measured memory_bytes: 31256
import sys
import copy
def solve():
    sys.setrecursionlimit(100000)
    input = sys.stdin.readline
    N, M = map(int, input().split())
    adjM = [[0] * N for i in range(N)] 
    for i in range(M):
        a, b = map(int, input().split())
        adjM[a - 1][b - 1] = 1
        adjM[b - 1][a - 1] = 1

    arrived = [False] * N
    ans = dfs(0, adjM, arrived, N)
    print(ans)

def dfs(now, adjM, arrived, N):
    arrived[now] = True
    if arrived == [True] * N:
        return 1
    
    cnt = 0
    for i in range(N):
        if adjM[now][i] == 1 and not arrived[i]:
            cnt += dfs(i, adjM, copy.deepcopy(arrived), N)
    
    return cnt


if __name__ == '__main__':
    solve()


Measured memory_bytes: 3444
#[allow(unused_imports)]
use std::io::{stdin, Read, StdinLock};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BinaryHeap};
#[allow(unused_imports)]
use std::vec::Vec;

#[allow(dead_code)]
const INF: i32 = 1000_000_000;
#[allow(dead_code)]
const INFLL: i64 = 1000_000_000_000_000_000;
#[allow(dead_code)]
const EPS: f64 = 1.0e-10;

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

impl<'a> Scanner<'a> {
    #[allow(dead_code)]
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner {cin: cin}
    }

    #[allow(dead_code)]
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
                    .skip_while(|c| c.is_whitespace())
                    .take_while(|c| !c.is_whitespace())
                    .collect::<String>();
        token.parse::<T>().ok()
    }

    #[allow(dead_code)]
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);
    let s: String = sc.read();
    let s: Vec<char> = s.chars().collect();
    println!("{}{}{}", s[0], s.len() - 2, s[s.len() - 1]);
}

Measured memory_bytes: 4352
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

# from numba import jit
# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, x = list(map(int, readline().split()))
    l = list(map(int, readline().split()))
    d = 0

    for i in range(n):
        d += l[i]
        if d > x:
            print(i + 1)
            sys.exit()

    print(n + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
N = input()
def rec(list1,initial,time):
    empty = []
    for e in list1:
        for b in [0,1,2]:
            if b == 0:
                e_copy = e + "3"
                empty.append(e_copy)
            elif b == 1:
                e_copy = e + "5"
                empty.append(e_copy)
            elif b == 2:
                e_copy = e + "7"
                empty.append(e_copy)
    list1 = empty[:]
    # initial + 1 がn回目のループ
    if initial + 1 >= time :
        return list1
    else:
        return rec(list1,initial + 1, time)
l1 = [""]
result = rec(l1,0,3)
for i in range(len(N)-3):
    result += rec(result,0,1)
result = [int(e) for e in result if e.count("3")*e.count("5")*e.count("7") >= 1]
result = list(set(result))
result.sort()
count = 0
for e in result:
    if int(N) < e:
        break
    count += 1
print(count)

Measured memory_bytes: 14996
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    int n; cin >> n;
    map<ll, ll> mp;
    REP(i, 0, n){
        int a; cin >> a;
        if(mp[a] > 0){
            cout << "NO" << endl;
            return 0;
        }else{
            mp[a]++;
        }
    }
    cout << "YES" << endl;
}

Measured memory_bytes: 12800
#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define ff first
#define ss second
#define setbits(x)          __builtin_popcountll(x)
#define lp(a,n) for(ll i=a; i<n; i++)
#define lpi(a,n) for(int i=a; i<n; i++)
#define w(t) int t; cin>>t; while(t--)
#define vi vector<int> 
#define vll vector<ll>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define inf 1e9
#define LB lower_bound
#define UB upper_bound
const int mod = 1000000007;
using namespace std;
ll gcd(ll a,ll b){
    if(a==0)return b;
    return gcd(b%a,a);
}
ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}

int prime[100007];
void SieveOfEratosthenes(int n) 
{ 
    memset(prime, -1, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
         
        if (prime[p] == -1) 
        { 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = p; 
        } 
    } 
    
} 
int lps(string s){
    int len = 0;
    int n = s.length();
    int dp[n];
    dp[0] = 0;
    for(int i=1; i<n; i++){
        if(s[i] == s[len]){
            len++;
            dp[i] = len;
            continue;
        }
        if(len!=0){
            len = dp[len-1];
            i--;
            continue;
        }
        dp[i]=0;
    }
    return dp[n-1];
}
 
ll power(unsigned ll x,unsigned  ll y) 
{ 
    ll res = 1;     
    while (y > 0) 
    { 
        if (y & 1) 
            res = res*x; 
   
        y = y>>1;
        x = x*x;  
    } 
    return res; 
}


int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
   int n;
   cin>>n;
   int a=0, b=0,c =0, d=0;
   for(int i=0; i<n; i++){
       string s;
       cin>>s;
       if(s=="AC") a++;
       else if(s=="WA") b++;
       else if(s=="RE") d++;
       else if(s=="TLE") c++;
   }
   cout<<"AC x "<<a<<endl;
   cout<<"WA x "<<b<<endl;
   cout<<"TLE x "<<c<<endl;
   cout<<"RE x "<<d<<endl;
}

Measured memory_bytes: 3624
A,B,C= map(int,input().split())

cnt = 0
if A%2==1 or B%2==1 or C%2==1:
    print(cnt)
elif A==B==C:
    print('-1')
else:
    flag = True
    while flag:
        A, B, C = (B+C)//2, (A+C)//2, (A+B)//2
        cnt += 1
        if A%2==0 and B%2==0 and C%2==0:    
            continue
        else:
            flag = False

    print(cnt)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

ll n;
vec a(100);
vec dp(1e5+10);
ll dfs(ll cur) {
  if(dp[cur]) return dp[cur];
  ll res=1;
  set<ll> cnt;
  for(ll i=0;i<n;i++) {
    if(cur-a[i]>=0) cnt.insert(dfs(cur-a[i]));
  }
  while(cnt.count(res)) res++;
  return dp[cur]=res;
}

int main() {
  ll k;
  cin >> n >> k;
  for(ll i=0;i<n;i++) cin >> a[i];
  dp[0]=1;
  if(dfs(k)!=1) cout << "First" << endl;
  else cout << "Second" << endl;
}

Measured memory_bytes: 13568
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        n %= 10;
        switch (n) {
            case 2:
            case 4:
            case 5:
            case 7:
            case 9:
                System.out.println("hon");
                break;
            case 0:
            case 1:
            case 6:
            case 8:
                System.out.println("pon");
                break;
            default:
                System.out.println("bon");
        }
    }
}


Measured memory_bytes: 35712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define X first
#define Y second
#define REP(i,a) for(int i=0;i<a;++i)
#define REPP(i,a,b) for(int i=a;i<b;++i)
#define FILL(a,x) memset(a,x,sizeof(a))
#define foreach( gg,itit )  for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define mp make_pair
#define pb push_back
#define all(s) s.begin(),s.end()
#define present(c,x) ((c).find(x) != (c).end())
const double EPS = 1e-8;
const int mod = 1e9+7;
const int N = 1e6+10;
const ll INF = 1e18;

//#define DEBUG
ll power(ll x,ll y){
  ll t=1;
  while(y>0){
    if(y%2) y-=1,t=t*x%mod;
    else y/=2,x=x*x%mod;
  }
  return t;
}
#ifdef DEBUG
#define dprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#else
#define dprintf(fmt,...)
#endif

ll arr[N];
ll dp[N];
int main(){
  int n; ll a ,b; scanf("%d%lld%lld",&n,&a,&b);
  REP(i,n) scanf("%lld",&arr[i]);
  ll ans=0;
  REP(i,n-1) ans+=min(b,a*(arr[i+1]-arr[i]));
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e9;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
typedef pair<double,double> point;
const ll MAX = 200005;
constexpr ll nx[8] = {1,0,-1,0,1,-1,1,-1};
constexpr ll ny[8] = {0,1,0,-1,1,1,-1,-1};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h,w;
    cin >> h >> w;
    vector<vector<ll>> a(h,vector<ll>(w));
    rep(i,h) rep(j,w) cin >> a[i][j];
    ll x = 0,y = 0;
    vector<vector<ll>> ans;
    bool f = 0;
    rep(i,h*w-1){
        ll nx = x,ny = y;
        if (x%2 == 0){
            if (y < w-1) ny++;
            else nx++;
        }
        else{
            if (y > 0) ny--;
            else nx++;
        }
        if (f&&(a[x][y]%2)) f = 0;
        else if ((!f)&&(a[x][y]%2)) f = 1;
        if (f) ans.push_back({x+1,y+1,nx+1,ny+1});
        x = nx;
        y = ny;
    }
    PRINT(ans.size());
    for (auto i:ans){
        cout << i[0] << " " << i[1] << " " << i[2] << " " << i[3] << endl;
    }
}


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

#define ll long long int
#define MAXN 100005
#define pb push_back

struct duo
{
    int t, d;
};

int MX[MAXN];
duo A[MAXN];
vector<int> V1, V2;

bool compd(duo d1, duo d2)
{
    return(d1.d > d2.d);
}

bool compt(duo d1, duo d2)
{
    return(d1.t < d2.t || d1.t == d2.t && d1.d > d2.d);
}

bool compr(int a, int b)
{
    return(a > b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i].t >> A[i].d;
        if (A[i].d > MX[A[i].t]) MX[A[i].t] = A[i].d;
    }
    sort(A, A + N, compd);
    ll res = 0;
    for (int i = 0; i < K; i++)
    {
        res += A[i].d;
        MX[A[i].t] = 0;
    }
    sort(A, A + K, compt);
    ll x = 1;
    for (int i = 1; i < K; i++)
    {
        if (A[i].t != A[i - 1].t) x++;
        else V1.pb(A[i].d);
    }
    res += x * x;
    for (int i = 1; i <= N; i++) if (MX[i]) V2.pb(MX[i]);
    sort(V1.begin(), V1.end());
    sort(V2.begin(), V2.end(), compr);
    int lim = V1.size();
    if (V2.size() < lim) lim = V2.size();
    ll cur = res;
    for (int i = 0; i < lim; i++)
    {
        cur += 2 * (x++) + 1 + V2[i] - V1[i];
        if (cur > res) res = cur;
    }
    cout << res << '\n';
    return(0);
}

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

int main(){
  
  int n;
  
  cin >> n;
  
  int a[n] ;
  
  rep(i,n){
  	cin >> a[i] ;
  }
  int j=1;
  int i;
  for(i=0;i<n;i++){
  	if(a[i]==j){
    	j++;
    }
  }
  
  j--;
  
  if(j==0){
  	j=n+1;
  }
  
  cout << n-j << endl;
  
  
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
using namespace std;
int main(){
    string str1, str2;
    int n, taro=0, hanako=0;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> str1 >> str2;
        if(str1>str2){taro+=3;
        }else if(str1<str2){hanako+=3;
        }else{taro++; hanako++;
        }
    }    
    cout << taro << " " << hanako << endl;
}


Measured memory_bytes: 3144
#include<stdio.h>
#include<limits.h>

#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int prim(void);

int n, m, sum, M[N][N];

int main()
{
  int i, j, e;
  
  scanf("%d",&n);

  for(i = 0; i < n; i++)
    {
      for(j = 0; j < n; j++)
	{
	  scanf("%d",&e);
	  if(e == -1)M[i][j] = INT_MAX;
	  else M[i][j] = e;	       
	}
    }

  m = prim();

  printf("%d\n",m);
  
  return 0;
}


int prim(void)
{
  int i, u, v, mincost, d[N], p[N], color[N];

  for(u = 0; u < n; u++)
    {
      color[u] = WHITE;
      d[u] = INT_MAX;
      p[u] = -1;
    }

  d[0] = 0;

  while(1)
    {
      mincost = INT_MAX;
      for(i = 0; i < n; i++)
	{
	  if(color[i] != BLACK && d[i] < mincost)
	    {
	      mincost = d[i];
	      u = i;
	    }
	}
      if(mincost == INT_MAX)break;

      color[u] = BLACK;
      
      for(v = 0; v < n; v++)
	{
	  if(color[v] != BLACK && M[u][v] != INT_MAX)
	    {
	      if(M[u][v] < d[v])
		{
		  d[v] = M[u][v];
		  p[v] = u;
		  color[v] = GRAY;
		}
	    }
	}
    }

  for(i = 0; i < n; i++)
    {
      if(p[i] != -1)sum += M[i][p[i]];
    }
  
  return sum;
}



Measured memory_bytes: 2052
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <map>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;


int main() {

    int A,B;
    cin >> A >> B;
    int ans=1;

    int i=0;
    while(ans<B){
        ans--;
        ans += A;
        i++;
    }
    cout << i << endl;
    return 0;
}

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

int main(){
  int i;
  vector<int> v(5);
  rep(j,6){
    cin >> i;
    v.at(i)++;
  }
  if(v.at(1)<=2&&v.at(2)<=2&&v.at(3)<=2&&v.at(4)<=2){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15,        2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    cout << a[k - 1];
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<functional>
#include <random>
#include<iostream>
#include<iomanip>
using namespace std;



int main() {
	int K;
	int N;
	int A[200000];
	cin >> K >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	int maxdist = K - (A[N - 1] - A[0]);

	for (int i = 0; i < N - 1; i++) {
		if (maxdist < A[i + 1] - A[i]) { maxdist = A[i + 1] - A[i]; }
	}

	cout << K - maxdist;

}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define USE_LLONG_AS_INT
#ifdef USE_LLONG_AS_INT
#define int long long
#define inf (1ll<<60)
#else
#define inf (1<<30)
#endif
#define rep(i,n) for(int i=0;i<(n);i++)
#define Rep(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int h,w;
    cin>>h>>w;
    vector<string> s(h);
    rep(i,h)cin>>s[i];
    int n=h*w;
    int g[n][n];
    rep(i,n)rep(j,n)g[i][j]=i==j?0:inf;
    rep(i,h){
        rep(j,w){
            if(s[i][j]=='#')continue;
            if(j+1<w&&s[i][j+1]=='.')g[i*w+j][i*w+j+1]=g[i*w+j+1][i*w+j]=1;
            if(j>0&&s[i][j-1]=='.')g[i*w+j][i*w+j-1]=g[i*w+j-1][i*w+j]=1;
            if(i+1<h&&s[i+1][j]=='.')g[i*w+j][(i+1)*w+j]=g[(i+1)*w+j][i*w+j]=1;
            if(i>0&&s[i-1][j]=='.')g[i*w+j][(i-1)*w+j]=g[(i-1)*w+j][i*w+j]=1;
        }
    }
    rep(k,n)rep(i,n)rep(j,n){
        if(g[i][j]>g[i][k]+g[k][j]){
            g[i][j]=g[i][k]+g[k][j];
        }
    }
    int ans=0;
    rep(i,n)rep(j,n){
        if(g[i][j]==inf)continue;
        ans=max(ans,g[i][j]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1664
n=int(input())
W=[input() for _ in range(n)]
end=W[0][-1]
Flag=1
exp=[W[0]]
for w in W[1:]:
    start=w[0]
    if end!=start or w in exp:
        Flag=0
        break
    end=w[-1]
    exp.append(w)
print('Yes' if Flag==1 else 'No')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define N 100005
int seg[4*N];
int mul(int a, int b)
{
    return a*b%mod;
}
int mypower(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b%2)
            ans = mul(ans, a);
        b=b/2;
        a=mul(a,a);
    }
    return ans;
}
void update(int st, int l, int r, int idx, int arr[], int val)
{
    if(l == r)
    {
        seg[st] = arr[l] = val;
        return;
    }
    int mid = (l+r)/2;
    if(idx <= mid)
        update(2*st+1, l, mid, idx, arr, val);
    else
        update(2*st+2,mid+1, r, idx, arr,val);
    seg[st] = min(seg[2*st+1],seg[2*st+2]);    
}
int query(int st, int l, int r, int ql, int qr)
{
    if(l > qr || r < ql)
    {
        return 0;
    }
    if(l >= ql && r <= qr)
        return seg[st];
    int mid = (l+r)/2;
    return min(query(2*st+1, l, mid, ql, qr), query(2*st+2, mid+1, r, ql, qr));
}

signed main() {
    int n;
    cin >> n;
    int arr[n];
    int i, sum = 0;
    int freq[100001] = {0};
    for(i=0;i<n;i++)
    {
        cin >> arr[i];
        sum+=arr[i];
        freq[arr[i]]++;
    }
    int q;
    cin >> q;
    while(q--)
    {
        int b, c;
        cin >> b >> c;
        sum-=b*freq[b];
        sum+=c*freq[b];
        freq[c]+=freq[b];
        freq[b] = 0;
        cout << sum << '\n';
    }
        
}

Measured memory_bytes: 5188
#include <iostream>

using namespace std;

int main()
{
    constexpr auto N = 50021, PN = 5134;
    bool checked[N+1] = {};
    int primes[PN] = {};
    for( int i=2, ii=0; i<=N; ++i ) {
        if ( !checked[i] ) {
            primes[ii++] = i;
            for( int j=i; j<N; j+=i ) {
                checked[j] = true;
            }
        }
    }

    int n;
    while( cin >> n ) {
        for( int i=0; i<PN; ++i ) {
            if ( primes[i] >= n ) {
                cout << primes[i-1] << " " << primes[i+(primes[i] == n)] << endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(int argc,char ** argv){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n , k;
  	cin >> n;
  	long long h[n][3] , dp[n][3];
  	for(int i = 0 ; i < n ; i++){
  		cin >> h[i][0] >> h[i][1] >> h[i][2]; 
  	}
  	dp[0][0] = h[0][0];
  	dp[0][1] = h[0][1];
  	dp[0][2] = h[0][2];
  	for(int i = 1 ; i < n ;i++){
  		for(int j = 0 ; j < 3 ; j++){
  			if(j == 0)
  				dp[i][j] = max(dp[i - 1][1] , dp[i - 1][2]);
  			if(j == 1)
  				dp[i][j] = max(dp[i - 1][0] , dp[i - 1][2]);
  			if(j == 2)
  				dp[i][j] = max(dp[i - 1][1] , dp[i - 1][0]);
  			dp[i][j] += h[i][j];
  		}
  	}
  	cout << max({dp[n - 1][0] , dp[n - 1][1] , dp[n - 1][2]}) << endl;
   
	return 0; 
}

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

int main(){
  int L,R,d;
  cin >> L >> R >> d;
  
  int answer = 0;
  for (int i=L ; i<R+1 ; i++){
    if (i%d == 0)
      answer++;
  }
  cout << answer << endl;
}

Measured memory_bytes: 3564
#include <iostream>
#include <string>
#include <atcoder/all>
#include <vector>
using ll=long long;
using namespace std;
using namespace atcoder;

int op(int a,int b){return max(a,b);}
int e(){return 0;}

int main(){
    int N,K;
    cin>>N>>K;

    vector<int> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }

    int size=3000001;
    segtree<int,op,e> seg(size);

    for(int i=0;i<N;i++){
        int maxnum=seg.prod(max(A[i]-K,0),min(A[i]+K+1,size));
        seg.set(A[i],maxnum+1);
    }

    int ans=0;
    for(int i=1;i<size;i++){
        int tmp=seg.get(i);
        if(ans<tmp){
            ans=tmp;
        }
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 48964
N = int(input())

ans = {}
M = 1
for _ in range(N):
    word = input()
    tmp = ans.get(word)
    if tmp == None:
        ans[word] = 1
    else:
        ans[word] = tmp + 1
        if tmp + 1 > M:
            M = tmp + 1

tmp = sorted(list(ans.keys()))
for t in tmp:
    if M == ans.get(t):
        print(t)

Measured memory_bytes: 32988
#include<stdio.h>
#include<math.h>

#define PI 3.1415926535

int main(void){
  double a,b,c,h;
  double S;
  double L;
  double buf;
  
  scanf("%lf%lf%lf", &a, &b, &c);
  c = c/180*PI;
  
  S = a*sin(c)*b/2;
  buf = pow(a,2)+pow(b,2)-2*a*b*cos(c);
  L = a+b+sqrt(buf);
  h = b*sin(c);

  printf("%f\n%f\n%f\n",S ,L ,h);
  
  return 0;
}

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const ll mod=1000000007;
//head

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

    int n;
    cin >> n;
    cout << fixed;
    cout << setprecision(10);
    vector<double> dp(n+1);
    dp[0] = 1;

    rep(i,0,n) {
        double p;
        cin >> p;
        for(int j = i + 1; j >= 0; j--) {
            if(j == 0) {
                dp[j] = dp[j]*(1-p);
            } else {
                dp[j] = dp[j-1]*(p) + dp[j]*(1-p);
            }
        }
    }
    double prob = 0;
    for(int i = 0; i <= n; i++) {
        if(i > n - i) prob += dp[i];
    }
    cout << prob << endl;
    return 0;
}


Measured memory_bytes: 256
// C++ 14
#include <bits/stdc++.h>
using namespace std;
template <typename T>  ostream& operator<<(ostream& os, const vector<T>& v)  {  os << "[";  for (int i = 0; i < v.size(); ++i) {  os << v[i];  if (i != v.size() - 1)  os << ", ";  }  os << "]";  return os;  }
template <typename T> void print(T v, string s = "\n") { cout << v << s; }
template <typename T> void in(T& v) { cin >> v; }
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)


int main() {
  int n;in(n);
  ll G[n][n];
  loop(i,0,n) loop(j,0,n) in(G[i][j]);
  
  ll ans = 0;
  // 辺i->jがいるかをチェックする. いるなら辺の重みを加える.
  // いる <=> i->jよりも重みの小さいk->jが無い.
  loop(i,0,n-1) loop(j,i+1,n) {
    bool ok = true;
    loop(k,0,n) {
      if (k==i or k==j) continue;
      // print(vector{ i, j, k});
      
      if (G[i][j] > G[i][k] + G[k][j]) {
        print(-1);
        return 0;
      }
      
      if (G[i][j] == G[i][k] + G[k][j]) {
        ok = false;
        break;
      }
    }
    if (ok) ans += G[i][j];
  }
  print(ans);
  return 0;
}


Measured memory_bytes: 4332
#include<algorithm>
#include<string>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<utility>
#include<functional>
#include<cassert>
#include<cmath>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<ll> vint;
typedef vector<vint> vvint;
#define PI 3.1415926535;
#define MOD 1000000007;

int main(void) {
	ll n, sum = 0, h=0,k=0;
	cin >> n;
	vint a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int i = 0, j = n-1;
	while (i <= j){
		if (h > k) {
			k += a[j];
			j--;
		}
		else {
			h += a[i];
			i++;
		}
	} 
	if (h > k) {
		cout << h - k;
	}
	else {
		cout << k - h;
	}
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int K;
  string text;
  cin >> K >> text;
  
  if(text.size() <= K){
  	cout << text << endl;
  }else{
  	for(int i=0; i<K; i++){
      cout << text.at(i);
    }
    cout << "..." << endl;
  }
}

Measured memory_bytes: 3600
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

const int N = 3005;
LL dp[N][N];
int a[N];

int main() {
	int n;
	scanf("%d", &n);
	REP(i, n)scanf("%d", &a[i]);
	FOR(w, 1, n + 1) {
		REP(i, n - w + 1) {
			dp[i][i + w] = max(a[i] - dp[i + 1][i + w], a[i + w - 1] - dp[i][i + w - 1]);
		}
	}
	cout << dp[0][n] << endl;
	return 0;
}

Measured memory_bytes: 70144
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
    int n, i, p, d, maxd, maxp;
    for(;;out.println(maxp + " " + maxd)){
      n = sc.nextInt(); if(n == 0)break;
      maxd = -1; maxp = -1;
      for(;n-- > 0;){
        p = sc.nextInt();
        d = sc.nextInt() + sc.nextInt();
        if(d > maxd){
          maxd = d; maxp = p;
        }
      }
    }

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 161492
## import
from collections import deque # キュー、スタックに利用
import itertools
import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用 # Pypy3ではimport不可
import sys

## 初期設定
# input = sys.stdin.readline # 標準入力の高速化に利用
sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = False

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

AB = [list(map(int, input().split())) for _ in range(m)]

## 隣接リスト表現でグラフを表現する
# 空の2次元リストの初期化 行数n * 列数0
M = [[] for _ in range(n)]
for a,b in AB:
    M[a-1].append(b-1)
    M[b-1].append(a-1)

if is_debug:
    for row in M:
        print(row)
    print('-----------')

def main():
    '''メイン処理'''

    ok_count = 0
    # 全パターンの順列（要素が同じでも、順番が異なれば異なるとみなすもの）を生成し、
    # 一つずつ、始点から終点までたどり着けるかチェック
    for permutation in itertools.permutations(range(1,n)):
        move_list = list(permutation)
        if is_debug:
            print(move_list)

        # この順列で終点までたどり着けるかチェック
        move_count = 0
        now_n = 0 # 始点は必ず0
        for next_n in move_list:
            if next_n in M[now_n]:
                now_n = next_n
                move_count += 1
            else:
                break
        if move_count == len(move_list):
            ok_count += 1
    
    print(ok_count)
            

if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()


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


int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a+b > c+d) cout << "Left" << endl;
  else if (a+b == c+d)cout << "Balanced" << endl;
  else cout << "Right" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

bool cnt[1000010];

int main() {
	int n;
	cin >> n;
	map<int, int> a;
	int m;
	for (int i = 0; i < n; i++) {
		cin >> m;
		if (!a.count(m))
			a.emplace(m, 1);
		else
			a[m]++;
	}
	int ans = 0;
	for (auto x : a) {
		for (int i = x.first * 2; i < 1000010; i += x.first)
			cnt[i] = true;
	}
	for (auto x : a) {
		if (x.second != 1) continue;
		if (!cnt[x.first]) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 13860
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

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

	std::map<int, int>cnt;
	++cnt[a];
	++cnt[b];
	++cnt[c];
	++cnt[d];
	if (cnt[1] == 1 && cnt[9] == 1 && cnt[7] == 1 && cnt[4] == 1) out << "YES" << std::endl;
	else out << "NO" << std::endl;
}


Measured memory_bytes: 764
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
set<string> c;
map<ll,ll> mp;
const ll inf=(1e18);
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
ll dp[100005];
int main(){
string s;
cin>>s;
bool ok=true;
for(int i=0;i<s.size();i++){
    if(i%2==0&&s[i]=='L')ok=false;
    else if(i%2==1&&s[i]=='R')ok=false;
}
if(ok)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep(i,n) rep2(i,0,n)
#define debug(x) cout << x << endl
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
template<typename T> struct V : vector<T> { using vector<T>::vector; };
V() -> V<int>;
V(size_t) -> V<int>;
template<typename T> V(size_t, T) -> V<T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1<<30;
const ll LINF = 1LL<<61;
const ll MOD = 1000000007;

int main()
{
    int n, k;
    cin >> n >> k;
    V a(n);
    rep(i,n) cin >> a[i];
    V dp(k+1); //0:必敗 1:必勝
    for(int i = 1; i <= k; i++)
    {
        int f = false; // 遷移先に必敗が存在しないならば、必敗
        for(auto t:a)
        {
            int ni = i - t;
            if(ni < 0) continue;
            if(dp[ni] == 0) f = 1;
        }
        dp[i] = f;
    }
    // debug(dp);
    if(dp[k]) cout << "First" << endl;
    else cout << "Second" << endl;

    return 0;
}

Measured memory_bytes: 3724
#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long ll;

int main() {
	
	string str;
	int cnt = 0;

	cin >> str;

	if(str.size() % 2 != 0){
		for (int i = 0; i < str.size() / 2; i++) {
			if (str.at(i) != str.at(str.size() - 1 - i)) cnt++;
		}
	}
	else {
		for (int i = 0; i < str.size() / 2; i++) {
			if (str.at(i) != str.at(str.size() - 1 - i)) cnt++;
		}
	}

	cout << cnt << endl;


	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
int main() {
	int n , k;
  	scanf("%d %d", &n, &k);
  	long double ans = 0., aux;
  	for (int i = 1, j; i<=n; ++i) {
    	j = i;
      	aux = 1.;
      	while (j <= k-1) {
        	aux *= 0.5;
            j<<=1;
        }
      	ans += aux;
    }
    double res = ans / n;
  	printf("%.12lf\n", res);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const int m=1e9+7;
int w,h;
char mat[1000][1000];
vector<vector<int>> dp(2000,vector<int>(2000));
int d[2][2]={{1,0},{0,1}};
bool valid(int x,int y){
    if(x<0||x>=w||y<0||y>=h){
        return false;
    }
    if(mat[x][y]=='#'){
        return false;
    }
    return true;
}
int calc(int i,int j){
    if(i==w-1 && j==h-1){
        return 1;
    }
    if(dp[i][j]!=-1){
        return dp[i][j];
    }
    int ans=0;
    for(int k=0;k<2;k++){
        int x1=i+d[k][0];
        int y1=j+d[k][1];
        if(valid(x1,y1)){
            ans+=calc(x1,y1)%m;
            ans%=m;
        }
    }
    return dp[i][j]=ans;
}
void solve(){
    cin>>w>>h;
    for(int i=0;i<w;i++){
        for(int j=0;j<h;j++){
            cin>>mat[i][j];
            dp[i][j]=-1;
        }
        cout<<'\n';
    }
    int result=calc(0,0);
    cout<<result<<'\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 17152
import java.io.*;
public class Main{
public static void main(String[] args){
//  int t = Integer.parseInt(args[0]);
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String str = null;
try{
  str = br.readLine();
  br.close();
} catch (IOException e){
  e.printStackTrace();
}
  int t = Integer.parseInt(str);
  System.out.println(t*t*t);
}

}



Measured memory_bytes: 24300
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define rep(i, j, n) for (int i = (j); i < (n); ++i)
using namespace std;
using i32 = int32_t;
using i64 = int64_t;

int main()
{
  i32 a, b;
  cin >> a >> b;

  i32 ans = 0;
  rep(i, a, b + 1)
  {
    string s = to_string(i);
    string t = s;
    reverse(t.begin(), t.end());
    if (s == t)
      ++ans;
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 3684