akhauriyash/Code-Regression huggingface dataset:
for c in range(1,51):
    W = int(input())
    if W == 0: break
    N = int(input())
    dp = [0 for w in range(W+1)]
    for i in range(N):
        v,w = map(int,input().split(','))
        for j in range(W-w,-1,-1):
            if dp[j] == 0 and j > 0: continue
            dp[j+w] = max(dp[j+w], dp[j] + v)
    ansv = answ = 0
    for w,v in enumerate(dp):
        if v > ansv:
            ansv = v
            answ = w
    print('Case ' + str(c) + ':')
    print(ansv)
    print(answ)



Measured memory_bytes: 5624
n = int(input())
L = list(map(int,input().split()))
dp = [0]*((10**6)+1000)
for i in L:
    dp[i] +=1

one = []
for i in range(10**6+1000):
    if dp[i] == 1:
        one.append(i)

dp = [0]*((10**6)+1000)
a = list(set(L))
for i in a:
    for j in range(2*i,10**6+1000,i):
        dp[j] = 1

ans = 0
for i in one:
    if dp[i] == 0:
        ans +=1
print(ans)


Measured memory_bytes: 47460
import java.util.Scanner;

public class Main {

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

        final int W = sc.nextInt();
        final int H = sc.nextInt();
        final int N = sc.nextInt();

        final int[][] area = new int[W][H];
        for (int i = 0; i < W; i++) {
            for (int j = 0; j < H; j++) {
                area[i][j] = 1;
            }
        }

        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int a = sc.nextInt();

            switch (a) {
                case 1:
                    for (int j = 0; j < x; j++) {
                        for (int k = 0; k < H; k++) {
                            area[j][k] = 0;
                        }
                    }
                    break;
                case 2:
                    for (int j = x; j < W; j++) {
                        for (int k = 0; k < H; k++) {
                            area[j][k] = 0;
                        }
                    }
                    break;
                case 3:
                    for (int j = 0; j < W; j++) {
                        for (int k = 0; k < y; k++) {
                            area[j][k] = 0;
                        }
                    }
                    break;
                case 4:
                    for (int j = 0; j < W; j++) {
                        for (int k = y; k < H; k++) {
                            area[j][k] = 0;
                        }
                    }
                    break;
            }
        }

        int ans = 0;
        for (int i = 0; i < W; i++) {
            for (int j = 0; j < H; j++) {
                ans += area[i][j];
            }
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 23028
n,k = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**9
dp = [INF]*n
dp[0] = 0

for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(
            dp[i],
            dp[j]+abs(h[i]-h[j])
        )
print(dp[-1])


Measured memory_bytes: 84656
N,K = map(int,input().split())

# 1からNまでにmodKでiとなるものがいくつあるか数えておく。
num = [0 for _ in range(K)]
for i in range(1,N+1):
  num[i%K] += 1

ans = 0
# aを決め打ちすると、a+b=0modK,c+a=0modKよりb,cが定まる。
# それがb+c=0modKを満たすかチェックする。
for a in range(K):
  b = (K-(a%K))%K
  c = (K-(a%K))%K
  if (b+c)%K != 0:
    continue
  ans += num[a]*num[b]*num[c]
print(ans)

Measured memory_bytes: 52336
class itp1_2b:
    def out(self,a,b,c):
        if a<b and b<c:
            print "Yes"
        else :
            print "No"
if __name__=="__main__":
 ipt=map(int,raw_input().split(" "))
 run=itp1_2b()
 run.out(ipt[0],ipt[1],ipt[2])

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


def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    operations = list()

    # See:
    # https://atcoder.jp/contests/abc109/submissions/3154532
    for row in range(h):
        for col in range(w - 1):
            if a[row][col] % 2 == 1:
                operations.append((row + 1, col + 1, row + 1, col + 2))
                a[row][col] -= 1
                a[row][col + 1] += 1

    for row in range(h - 1):
        if a[row][w - 1] % 2 == 1:
            operations.append((row + 1, w, row + 2, w))
            a[row][w - 1] -= 1
            a[row + 1][w - 1] += 1

    n = len(operations)
    print(n)

    for i in range(n):
        y, x, y_dash, x_dash = operations[i]
        print(y, x, y_dash, x_dash)


if __name__ == '__main__':
    main()


Measured memory_bytes: 26652
#include<bits/stdc++.h>
using namespace std;
string s;
int len,gs;
int main()
{
   cin>>s;
   len=s.size();
   for(int i=0;i<s.size();i++)
   {
		if(s[i]=='S') gs++;
		if(gs>0&&s[i]=='T') gs--,len-=2;
   }
   cout<<len;
   return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=300005;

inline int read(){
	int x=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x;
}

void W(int x){ if(x>=10) W(x/10); putchar(x%10+'0');}

int n,a[N],c[N],l,ans[N];

inline void update(int pos,int val){
	if(val>a[pos]) c[pos]=a[pos],a[pos]=val;
	else if(val>c[pos]) c[pos]=val;
}

inline void solve(){
	for(int i=0,to;i<l;i++)
	    for(int j=0;j<n;j++) if(!((1<<i)&j)){
	    	to=j|(1<<i);
	    	
			update(to,a[j]);
			update(to,c[j]);
		}
}

int main(){
	scanf("%d",&n),l=n,n=1<<n;
	for(int i=0;i<n;i++) a[i]=read(),c[i]=0;
	
	solve();
	
	for(int i=1;i<n;i++){
		ans[i]=max(ans[i-1],a[i]+c[i]);
		W(ans[i]),puts("");
	}
	
	return 0;
}

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

class Node {
  public:
    bool is_visited;
    vector<int> children;
    Node() {
      is_visited = false;
    }
};

int main()
{
  int n, x, y;
  cin >> n >> x >> y;
  vector<Node> node(n);
  for (int i = 1; i < n; i++) {
    node.at(i-1).children.push_back(i);
    node.at(i).children.push_back(i-1);
  }
  node.at(x-1).children.push_back(y-1);
  node.at(y-1).children.push_back(x-1);
  vector<int> res(n+1);
  for (int i = 0; i < n; i++) {
    queue<int> q;
    int d = 0;
    q.push(i);
    q.push(-1);
    while (true) {
      int id = q.front();
      q.pop();
      if (id == -1) {
        if (q.empty()) {
          break;
        }
        d++;
        q.push(-1);
        continue;
      }
      if (node.at(id).is_visited) {
        continue;
      }
      node.at(id).is_visited = true;
      res.at(d)++;
      for (int z : node.at(id).children) {
        q.push(z);
      }
    }
    for (auto& z : node) {
      z.is_visited = false;
    }
  }
  for (int i = 1; i < n; i++) {
    assert(res.at(i) % 2 == 0);
    cout << res.at(i) / 2 << '\n';
  }
  return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		int n = 0, m = 0;
		Scanner sc =new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();

		int time = 0;
		time = ((1900*m+100*(n-m))*(int)Math.pow(2, m));
		System.out.println(time);

	}

}


Measured memory_bytes: 23764
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main(){
    int n,x[100],y[100];
    cin >> n;
    for (int i=0; i<n; i++) cin >> x[i];
    for (int i=0; i<n; i++) cin >> y[i];
    
    double d[4];
    for (int i=0; i<4; i++) d[i]=0.0;
    
    for (int p=1; p<=3; p++){
        for (int i=0; i<n; i++){
            d[p] += pow(fabs(x[i]-y[i]),p);
        }
        d[p] = pow(d[p],1.0/p);
    }
     for (int i=0; i<n; i++){
         d[0] = (d[0]<fabs(x[i]-y[i])?fabs(x[i]-y[i]):d[0]);
     } 
     
     printf("%lf\n",d[1]);
     printf("%lf\n",d[2]);
     printf("%lf\n",d[3]);
     printf("%lf\n",d[0]);
     return 0;
}


Measured memory_bytes: 3336
#include "bits/stdc++.h"
using namespace std;
#ifdef ONLINE_JUDGE
#define trace(...)
#endif

using LL = long long;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int n; cin >> n;
	string s; cin >> s;
	int ans = 0;
	char prev = '$';
	for (char ch: s) {
		if (ch != prev) {
			prev = ch;
			ans++;
		}
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 512
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000009)
	sc.Split(bufio.ScanWords)
	s := Scanner()
	mod := make([]int, 13)
	mod[0] = 1
	d := 1000000007
	for i := 0; i < len(s); i++ {
		m := make([]int, 13)
		if s[i:i+1] == "?" {
			for j := 0; j <= 9; j++ {
				for k := 0; k < 13; k++ {
					x := (k*10 + j) % 13
					m[x] = (m[x] + mod[k]) % d
				}
			}
		} else {
			n, _ := strconv.Atoi(s[i : i+1])
			for k := 0; k < 13; k++ {
				x := (k*10 + n) % 13
				m[x] = mod[k] % d
			}
		}
		copy(mod, m)
	}
	fmt.Println(mod[5])
}


Measured memory_bytes: 896
fun main(args: Array<String>) {
    readInteger()
    calc(0, readLine()!!).let(::println)

}

tailrec fun calc(count: Int, s: String): Int {
    if (s.length < 3) {
        return count
    }

    return calc(calcNextCount(count, s), s.substring(1))
}

fun calcNextCount(count: Int, s: String) = if (s.startsWith("ABC")) count + 1 else count

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)


Measured memory_bytes: 31840
module ArrayL = ArrayLabels
module ListL = ListLabels

let dbg = Printf.printf "[debug]%s"

let max_num = 100_000_000_000

let id = fun x -> x
let tuple2 x y = (x,y)
let tuple3 x y z = (x,y,z)
let succ x = x + 1
let pred x = x - 1

let (++) n m =
  let rec aux i =
    if i = m then [m]
    else i :: aux (i+1) in
  if n > m then [] else aux n

let (++^) n m = n ++ (m-1)

let scan fmt f = Scanf.sscanf (read_line ()) fmt f

let scan_list ~sep cnv =
  let line = read_line () in
  Str.split (Str.regexp_string sep) line
  |> List.map cnv

let scan_lines n fmt f =
  List.map (fun _ -> scan fmt f) (0++^n)

let scan_matrix n m e conv =
  let arr = Array.make_matrix n m e in
  Array.iteri (fun i line ->
      let s = Scanf.Scanning.from_string @@ read_line () in
      Array.iteri (fun j _ ->
          arr.(i).(j) <- Scanf.bscanf s " %s" conv;
        ) line) arr; arr

let rec powerset = function
  | [] -> [[]]
  | hd::tl ->
    let pws =  powerset tl in
    pws @ ListL.map pws ~f:(fun pw -> hd::pw)

let permutations l =
  let rec interleave x = function
    | [] -> [[x]]
    | (hd::tl) as l ->
      (x::l) :: (interleave x tl |> ListL.map ~f:(fun l -> hd::l)) in
  let rec aux = function
    | [] -> [[]]
    | a::rest ->
      aux rest |> ListL.map ~f:(interleave a) |> List.concat in
  aux l

let between n x m = n <= x && x < m

let string_to_list s =
  List.map (String.get s) (0 ++^ String.length s)


let rec dfs mat h w visited i j n =
  ListL.iter [(-1,-1);(-1,0); (-1,1);(0,-1);(0,1);(1,-1);(1,0);(1,1)] ~f:(fun (dx,dy) ->
      let i,j = i + dx, j + dy in
      if between 0 i h && between 0 j w && mat.(i).(j) = 1 && visited.(i).(j) = 0 then
        (visited.(i).(j) <- n;
         dfs mat h w visited i j n))

let () =
  let rec solve () =
    let (w,h) = scan "%d %d" tuple2 in
    if w = 0 && h = 0 then ()
    else
      let mat = scan_matrix h w 0 int_of_string in
      let m = Array.make_matrix h w 0 in
      let n = ref 1 in
      ListL.iter (0++^h) ~f:(fun i ->
          ListL.iter (0++^w) ~f:(fun j ->
              if mat.(i).(j) = 1 && m.(i).(j) = 0 then
                (m.(i).(j) <- !n;
                 dfs mat h w m i j !n ;
                 incr n)));
      let f = ArrayL.fold_left ~init:0 ~f:(max) in
      ArrayL.map m ~f:f |> f
      |> Printf.printf "%d\n";
      solve () in
  solve ()



Measured memory_bytes: 4504
# E - Knapsack 2
def knapsack_heavy(limit: int, weight: list, value: list) -> int:
    lim = sum(value)
    dp = [0] + [1 << 30] * lim  # dp[i] := minimum weight at value i
    for w, v in zip(weight, value):
        for cur_v in range(lim, v - 1, -1):
            dp[cur_v] = min(dp[cur_v], dp[cur_v - v] + w)
    ret = max(v for v, w in enumerate(dp) if w <= limit)
    return ret


def main():
    N, W, *WV = map(int, open(0).read().split())
    print(knapsack_heavy(W, WV[::2], WV[1::2]))


if __name__ == "__main__":
    main()


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

pl = []


for i in range(N):

    pl.append(int(input()))


max = 0

t = 0

for j in range(N):

    if max < pl[j]:
        max = pl[j]
        
    t = t + pl[j]

#print(max)

t = t + (max / 2) - max

print(int(t))


Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Long> a = new ArrayList<>();
        IntStream.range(0, n).forEach(i -> a.add(sc.nextLong()));

        final String INIT = "INIT";
        final String INC = "INCREMENT";
        final String DEC = "DECREMENT";
        Long prev = 0L;
        String state = INIT;
        Long count = 1L;
        for (int i = 0; i < a.size(); i++) {
            Long current = a.get(i);
            if (i == 0) {
                prev = current;
                continue;
            }
            if (state.equals(INIT)) {
                if (current > prev) {
                    state = INC;
                }
                if (current < prev) {
                    state = DEC;
                }
                prev = current;
                continue;
            }
            if (state.equals(INC) && current >= prev) {
                prev = current;
                continue;
            }
            if (state.equals(DEC) && current <= prev) {
                prev = current;
                continue;
            }
            prev = current;
            state = "INIT";
            count++;
        }
        System.out.println(count);
    }

}


Measured memory_bytes: 60224
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=1; i<=(int)(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int n;
    cin>>n;
    vi v(n+1,0);
    rep(i,n-1) {
        int a;
        cin>>a;
        a--;
        v[a]++;
    }
    rep(i,n) cout<<v[i]<<endl;
}

Measured memory_bytes: 4048
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
#include <iomanip>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 2;
const int MOD = 1000000007;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main() {
	int N;
	cin >> N;
	vi a(N);
	REP(i, N) {
		cin >> a[i];
	}
	int ans = 0, tmp = 10001;
	REP(i, N-1) {
		if (a[i] == a[i + 1]) {
			ans++;
			a[i + 1] = tmp++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int K = in.nextInt();
    double sum = 0;
    for (int i = 1; i <= N; i++) {
      if (K <= i) {
        sum++;
        continue;
      }
      int value = i, p = 1;
      while (value < (K + 1) / 2) {
        value *= 2;
        p++;
      }
      sum += Math.pow(0.5, p);
    }
    System.out.println(sum / N);
  }
}

Measured memory_bytes: 21332
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;




int main(){
    ll k;
    cin>>k;
    vector<vector<ll>> ans;
    if(k<=500){
        ans.resize(k,vector<ll>(k));
        for(int i=0;i<k;i++){
            for(int t=0;t<k;t++){
                ans[i][t]=(i+t)%k;
            }
        }
    }
    else{
        ll n=(k+1)/2;
        if(n&1){n++;}
        ans.resize(n,vector<ll>(n));
        for(int i=0;i<n;i++){
            for(int t=0;t<n;t++){
                ans[i][t]=(i+t)%n;
                if(i&1){ans[i][t]+=n;}
            }
        }
        for(int i=0;i<n;i++){
            for(int t=0;t<n;t++){
                if(ans[i][t]>=k){ans[i][t]-=n;}
            }
        }
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        for(int t=0;t<ans.size();t++){
            cout<<ans[i][t]+1;
            if(t+1!=ans.size()){cout<<" ";}
        }
        cout<<endl;
    }
    
    
    return 0;
}


Measured memory_bytes: 3200
package main

import (
	"fmt"
)

func main() {
	var (
		n          int
		alice, bob int
	)
	fmt.Scan(&n)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}

	for i := 0; i < n-1; i++ {
		for j := n - 1; j > i; j-- {
			if a[j] > a[j-1] {
				tmp := a[j]
				a[j] = a[j-1]
				a[j-1] = tmp
			}
		}
	}
	// alice
	for i := 0; i < n; i += 2 {
		alice += a[i]
	}
	// bob
	for i := 1; i < n; i += 2 {
		bob += a[i]
	}
	fmt.Println(alice - bob)
}


Measured memory_bytes: 512
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
#include <fstream>
#include <cassert>
using namespace std;
#pragma warning(disable : 4996)
typedef long long ll;



int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	cout << (n == m ? "Yes" : "No");
}

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

map<ll,ll>f;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,a,b,s=0,x;
    cin>>a>>b;
    while(1ll<<s <= b/a){
        s++;
    }
    cout<<s<<endl;
    ///576460752303423488
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,int> P;
const LL mod=1000000007;
const LL LINF=1LL<<62;
const LL INF=1<<17;

static const int MAX_SIZE = 1 << 20; //segment tree のサイズ。この実装では2べきにする必要がある。 2^17 ≒ 1.3 * 10^5

typedef long long Int;
int segMin[2 * MAX_SIZE - 1], segAdd[2 * MAX_SIZE - 1];

//区間[a, b)に値xを加算する.
void add(int a, int b, int x, int k = 0, int l = 0, int r = MAX_SIZE)
{
	if (r <= a || b <= l) return; //もし交差しない区間であれば終える.
	
	if (a <= l && r <= b){ //もし今みている区間[l, r)が[a, b)に完全に内包されていれば
		segAdd[k] += x;  //区間[l, r)にkを加算する.
		return;
	}
	
	add(a, b, x, k * 2 + 1, l, (l + r) / 2); //子の区間に(必要があれば)xを加算する.
	add(a, b, x, k * 2 + 2, (l + r) / 2, r); //〃

	//親の区間の最小値は, 子の区間の最小値 + 自分に一様に加算されている値 である.一様に加算される値は更新しなくて良い.
	segMin[k] = min(segMin[k * 2 + 1] + segAdd[k * 2 + 1], segMin[k * 2 + 2] + segAdd[k * 2 + 2]);
}

int getMin(int a, int b, int k = 0, int l = 0, int r = MAX_SIZE)
{
	if (r <= a || b <= l) return (INT_MAX);
	
	if (a <= l && r <= b) return (segMin[k] + segAdd[k]); //完全に内包されていれば,その区間の最小値を返す.
	
	int left = getMin(a, b, k * 2 + 1, l, (l + r) / 2); //子の区間の最小値を求める.
	int right = getMin(a, b, k * 2 + 2, (l + r) / 2, r); //子の区間の最小値を求める
	
	return (min(left, right) + segAdd[k]); //親の区間の最小値は, 子の区間の最小値 + 自分に一様に加算されている値 である (大切なので2回書きました!!)
	
}


int main(){
    int n,q;cin >> n >> q;
    string s;cin >> s;
    set<int> sb;
    int sum=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='('){
            sum++;
        }
        else{
            sum--;
            sb.insert(i);
        }
        add(i,i+1,sum);
    }
    for(int i=0;i<q;i++){
        int t;cin >> t;
        t--;
        if(s[t]=='('){
            add(t,n,-2);
            sb.insert(t);
            auto p=sb.begin();
            s[t]=')';
            s[*p]='(';
            sb.erase(*p);
            add(*p,n,2);
            cout << *p+1 << endl;
        }
        else{
            add(t,n,2);
            sb.erase(t);
            s[t]='(';
            int l=0,r=t;
            while(abs(r-l)>1){
                int m=(l+r)/2;
                if(getMin(m,n)>=2) r=m;
                else l=m;
            }
            s[r]=')';
            add(r,n,-2);
            sb.insert(r);
            cout << r+1 << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 13760
#include<bits/stdc++.h>
#define int long long int
#define rep(a,b,c) for(int a=b;a<c;a++)
#define repm(a,b,c) for(int a=(b-1);a>=c;a--)
#define pb push_back
#define str string
#define INF 1<<64
#define ff(i,n,b) fill(i,i+n,b)
#define sorts(v) sort(v.begin(),v.end())
#define sf(a) scanf("%d",&a)
#define down greater<int>()
#define sankaku(x,y)
#define ALL(v) (v).begin(), (v).end()
#define kiru substr// s.insort(0,"a"); s.substr(5,3) //5~3
#define asas(a,b) assign(a,b) ////amojimenibwodainyuu anoutinobkowodainyuu
using namespace std;
int replac(str s){double ans=0;rep(i,0,s.length()){ans+=(s[i]-'0')*pow(10,s.length()-i-1);}return (int)ans;}
typedef pair<int,int> pii;
vector<int> v[100005];
int n,d[100005]={0};
int f(int dp = 0,int edge = 0){
    if(!v[edge].size()){
       // cout << " jisshitu=hair " << endl;
        return dp;
    }else{
        int ans = v[edge].size()+dp;
        vector<int> sub;
        for(int e : v[edge]){
            sub.pb(f(dp+1,e));
        }
        sort(ALL(sub),greater<int>());
        int y = 0;
        rep(i,0,sub.size()){
            ///if(i>0&&sub[i-1]==sub[i]){
                y++;
            //}else{
              //  y = 0;
           // }
            ans = max(ans,y+sub[i]-1);
        }
        return ans;
    }
}
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    rep(i,1,n){
        int x;
        cin >> x;
        x--;
        v[x].pb(i);
    }

    cout << f() << endl;
    return 0;
}


Measured memory_bytes: 15104
package main

import (
	"fmt"
	"sort"
)

func tree(n, k int, h []int) int {
	sort.Ints(h)
	min := h[len(h)-1]
	for i := 0; i+k <= n; i++ {
		x, n := i+k-1, i
		diff := h[x] - h[n]
		if diff < min {
			min = diff
		}
	}
	return min
}

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	h := make([]int, n)
	for i := range h {
		fmt.Scan(&h[i])
	}
	fmt.Println(tree(n, k, h))
}


Measured memory_bytes: 5504
#!/usr/bin/env python3
import itertools
l = list(range(1, int(input()) + 1))
p = list(map(int, input().split()))
q = list(map(int, input().split()))
cnt_a = 1
cnt_b = 1
for i in itertools.permutations(l):
    if list(i) == p:
        a = cnt_a
    if list(i) == q:
        b = cnt_b
    cnt_a += 1
    cnt_b += 1
print(abs(a - b))


Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include<iomanip>
#include <cmath>

using namespace std;

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

    if(X>10500)
    {
        cout<<"1"<<endl;
        return 0;
    }

    int M[200000]= {0};

    int N = 20;
    for(int a = 0;a<=N;a++)
    {
        for(int b = 0;b<=99;b++)
        {
            for(int c = 0;c<=N;c++)
            {
                for(int d = 0;d<=N;d++)
                {
                    for(int e = 0;e<=N;e++)
                    {
                        for(int f = 0;f<=N;f++)
                        {
                            int ret = a*100+b*101+c*102+d*103+e*104+f*105;
                            if(M[ret]==0)
                            {
                                M[ret]=1;
                            }
                        }
                    }
                }
            }
        }
    }
    if(M[X]==0)
    {
        cout<<"0"<<endl;
    }
    else
    {
        cout<<"1"<<endl;
    }
    

    return 0;
}

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

stores = []
for i in range(N):
  A,B = map(int, input().split())
  stores.append([A,B])

stores.sort()
i = 0
amt = 0
while M > 0:
  if M < stores[i][1]:
    amt += stores[i][0] * M
    M =0
  else:
    amt += stores[i][0] * stores[i][1]
    M -= stores[i][1]
  i+=1

print(amt)

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

using namespace std;

const int N = 2e5 + 5;
const int M = 2e3 + 5;
const int mod = 1e9 + 7;

int n, a[N], b[N], fact[N], inv_fact[N], dp[M * 2][M * 2], ans = 0;

int binPow (int x, int y) {
    int ans = 1;
    while (y > 0) {
        if (y & 1) ans = (1LL * ans * x) % mod;
        x = (1LL * x * x) % mod;
        y >>= 1;
    }

    return ans;
}

void prep(){
    fact[0] = inv_fact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (1LL * i * fact[i - 1]) % mod;
        inv_fact[i] = binPow(fact[i], mod - 2);
    }
}

void add (int &x, int y) {
    x = (x + y) % mod;
}

int C (int n, int k) {
    int res = 1; res = 1LL * res * fact[n] % mod;
    res = 1LL * res * inv_fact[k] % mod;
    res = 1LL * res * inv_fact[n - k] % mod;

    return res;
}

int main(){
    scanf("%d", &n);
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i], &b[i]);
        dp[-a[i] + M - 5][-b[i] + M - 5]++;
    }

    prep();
    for (int i = 0; i < M * 2; i++) {
        for (int j = 0; j < M * 2; j++) {
            if (i) add(dp[i][j], dp[i - 1][j]);
            if (j) add(dp[i][j], dp[i][j - 1]);
        }
    }

    for (int i = 1; i <= n; i++) add(ans, dp[a[i] + M - 5][b[i] + M - 5]);
    for (int i = 1; i <= n; i++) ans = (ans - C(a[i] * 2 + b[i] * 2, a[i] * 2)) % mod;

    ans = (1LL * ans * binPow(2, mod - 2)) % mod;
    if (ans < 0) ans += mod;
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 66176
# ABC160_C
k,n=map(int,input().split())
a=list(map(int,input().split()))
# mid=(a[0]+a[-1])/2
d=[]
for i in range(n-1):
    d.append(a[i+1]-a[i])
# d.append(k-a[-1])
# d=[k-a[-1]]+d

# print(d)
ans=10**10
d=[k-a[-1]+a[0]]+d
d+=[k-a[-1]+a[0]]
# print(d)
for i in range(1,n):
    t=min(k-d[i-1],k-d[i+1])
    ans=min(t,ans)
print(ans)


Measured memory_bytes: 26444
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>

using namespace std;

int main(){

    string s;
    cin >> s;

    int len = s.size();
    if(len % 2 == 0){
        if(s[0] == s.back()){
            cout << "First" << endl;
        }
        else{
            cout << "Second" << endl;
        }
    }
    else{
        if(s[0] == s.back()){
            cout << "Second" << endl;
        }
        else{
            cout << "First" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define all(m) m.begin(), m.end()
#define uid uniform_int_distribution
#define init(m, x) memset(m, x, sizeof(m));
#define FILE ifstream in("input.txt");ofstream out("output.txt");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    fast;
    ll a; cin>>a;
    set<ll> s;
    ll cur = 0, o=1;
    for(; ; o++){
        cur = cur*10+7;
        cur %= a;
        if(cur==0) break;
        if(s.count(cur)){
            cout<<-1;
            return 0;
        }
        s.insert(cur);
    }
    cout<<o;
}

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

bool trans(string& S, string &T, int n){
    char s = S[n], t = T[n];
    for(int i=n; i<S.size(); i++){
        if(S[i] == s){
            S[i] = t;
        }
        else if(S[i] == t){
            S[i] = s;
        }
    }
    return true;
}
int changed[int('z')-int('a')];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    bool ans = true;
    
    string S, T;
    int N;
    cin >> S >> T;
    for(int n=0; n<S.size(); n++){
        if(S[n] != T[n]){
            if(changed[int(S[n])-int('a')] || changed[int(T[n])-int('a')]){
                ans = false;
                break;
            }
            changed[int(T[n])-int('a')] = 1;
            ans = trans(S, T, n);
            if(not ans)break;
        }
    }
    if(ans)cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 916
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

alias D = Tuple!(long, "sum", int, "i", int, "j", int, "k");

void main() {
    auto xs = readints;
    int x = xs[0], y = xs[1], z = xs[2], kk = xs[3];
    auto a = reads!long;
    auto b = reads!long;
    auto c = reads!long;

    a.sort!("a > b");
    b.sort!("a > b");
    c.sort!("a > b");
    auto pq = new BinaryHeap!(Array!D);
    bool[int[]] used;
    pq.insert(D(a[0] + b[0] + c[0], 0, 0, 0));
    while (kk > 0) {
        auto d = pq.front;
        pq.popFront();
        if ([d.i, d.j, d.k] in used) continue;

        writeln(d.sum);
        used[cast(immutable(int)[])[d.i, d.j, d.k]] = true;
        kk--;

        int i = d.i;
        int j = d.j;
        int k = d.k;
        if (i + 1 < a.length)
            pq.insert(D(a[i + 1] + b[j] + c[k], i + 1, j, k));
        if (j + 1 < b.length)
            pq.insert(D(a[i] + b[j + 1] + c[k], i, j + 1, k));
        if (k + 1 < c.length)
            pq.insert(D(a[i] + b[j] + c[k + 1], i, j, k + 1));
    }
}


Measured memory_bytes: 2812
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<28;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-8;
const int mod=1e9+7;
const vi emp;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int DX[8]={-1,-1,-1,0,0,1,1,1},DY[8]={1,0,-1,1,-1,1,0,-1};

int n,m;

int main(){
	cin>>n>>m;
	vi a(m),b(m);
	map<int,int> M;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		int y=x%m;
		a[y]++;
		M[x]++;
		if(M[x]!=0&&M[x]%2==0) b[y]++;
	}
	int ans=a[0]/2;
	for(int i=1;i<(m+1)/2;i++){
		int j=m-i;
		ans+=min(a[i],a[j]);
		if(a[i]>a[j]){
			a[i]-=a[j];
			ans+=min(a[i]/2,b[i]);
		}
		else{
			a[j]-=a[i];
			ans+=min(a[j]/2,b[j]);
		}
	}
	if(m%2==0) ans+=a[m/2]/2;
	cout<<ans<<endl;
}

Measured memory_bytes: 5888
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<random>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }

struct BIT0{
    vector<int> data;
    BIT0(int n): data(n + 1){ }
    void add(int idx, int num){
        // idx = max(0, min((int)data.size() - 1, idx));
        idx++;
        for(; idx < (int)data.size(); idx += idx & -idx){
            data[idx] += num;
        }
    }
    int sum(int idx){
        // idx = max(0, min((int)data.size() - 1, idx));
        idx++;
        int ret = 0;
        for(; idx; idx -= idx & -idx){
            ret += data[idx];
        }
        return ret;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    vector<int> as(n); cin >> as;
    auto as2 = as;
    sort(as2.begin(), as2.end());
    vector<int> as3(n);
    int in = 0, out = n;
    while(in + 1 < out){
        int piv = (in + out) / 2,
            num = as2[piv];
        for(int i = 0; i < n; i++){
            as3[i] = as[i] < num ? -1 : 1;
        }
        for(int i = 1; i < n; i++){
            as3[i] += as3[i - 1];
        }
        BIT0 bt(n * 2 + 1);
        ll acc = 0;
        bt.add(0 + n, 1);
        for(int i = 0; i < n; i++){
            acc += bt.sum(as3[i] + n);
            bt.add(as3[i] + n, 1);
        }
        printde(as3);
        printde(piv, acc, n * (n + 1) / 4);
        if(acc >= (n * (n + 1) + 2) / 4){
            in = piv;
        }else{
            out = piv;
        }
    }
    cout << as2[in] << '\n';
}


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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)
C = list(map(int, input().split()))
A = sum(C) - max(C)
C.sort()

ans = [None] * N
ans[0] = C.pop()
st = [0]
while st:
    now = st.pop()
    for to in edges[now]:
        if ans[to] == None:
            ans[to] = C.pop()
            st.append(to)

print(A)
print(*ans)


Measured memory_bytes: 5912
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef priority_queue<ll> pq;

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

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

int main() {
  int N, ans; cin >> N >> ans;
  for (int i = 1; i < N; i++) {
    int A; cin >> A;
    ans = gcd(ans, A);
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
	//入力を受け取る
	int D, T, S;
	cin >> D >> T >> S;

	//高橋君の移動時間を計算する
	double time = (double)D / S;

	//Tとtimeの大小関係に応じて出力をする
	if (T >= time) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}



Measured memory_bytes: 3616
n=int(input())
s=list(map(int,input().split()))
g=0
h=0
for i in range(n):
    if s[i]%2==0:
        g+=1
        if s[i]%3==0 or s[i]%5==0:
            h+=1
print("APPROVED" if g==h else "DENIED")



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

using namespace std;

int main(){
	long long a, b;
	cin>>a>>b;
	if (a * b <= 0)
		puts("Zero");
	else{
		if (a < 0 && ((b - a) % 2  == 0))
			puts("Negative");
		else
			puts("Positive");
	}
	return 0;
} 

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

int main() {
	int N;
	cin >> N;
	vector<int> a(N+2);
	a[0] = 0;
	int a_num = 0;
	for (int i = 1; i <= N; i++) {
		int b;
		cin >> b;
		if(a[a_num] != b){
			a_num++;
			a[a_num] = b;
		}
	}
	a.push_back(0);
	vector<int> kado;
	kado.push_back(0);
	for (int i = 1; i < a.size()-1; i++)
		if ((a[i] > a[i-1] && a[i] > a[i+1]) ||
			(a[i] < a[i-1] && a[i] < a[i+1]))
			kado.push_back(a[i]);
	vector<int> mountain;
	vector<int> valley;
	for (int i = 0; i < kado.size(); i++)
		if (i%2 == 1)
			mountain.push_back(kado[i]);
		else
			valley.push_back(kado[i]);
	sort(kado.begin(), kado.end());
	sort(mountain.begin(), mountain.end());
	sort(valley.begin(),valley.end());
	int ans = 0, max = 0;
	if(kado.size() == 1){
		max = 0;
		cout << max << endl;
		return 0;
	}
	int m = 0, b = 0;
	for(int i = 0; i < kado.size(); i ++){
		if (mountain[m] == kado[i]){
			m++;
			ans--;
		}
		if (valley[b] == kado[i]){
			b++;
			ans++;
		}
		if (kado[i] < kado[i+1])
			if (ans > max)max = ans;
	}
	cout << max << endl;
}


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

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vd;
typedef vector<vd> vvd;
const ll inf = pow(2, 31) - 1;
int main()
{
	ll n, x, y;
	cin >> n >> x >> y;
	x--; y--;
	vll ans(n, 0);
	vvll d(n, vll(n, inf));
	rep(i,n-1){
		d[i][i] = 0;
		d[i][i+1] = d[i+1][i] = 1;
	}
	d[n-1][n-1] = 0;
	d[x][y] = d[y][x] = 1;

	rep(i,n)REP(j,i,n){
		d[i][j] = min((ll)abs(i - j), abs(i-x) + 1 + abs(j-y));
	}
	rep(i,n)REP(j,i,n)ans[d[i][j]]++;
	rep(i,n-1)cout << ans[i + 1] << endl;
	return 0;
}

Measured memory_bytes: 31616
a,b,c = map(int, input().split())
x0=c
x1=a*c-b
x2=a*(x1-x0)+x1
x3=a*(x2-x1)+x2
x4=a*(x3-x2)+x3
x5=a*(x4-x3)+x4
x6=a*(x5-x4)+x5
x7=a*(x6-x5)+x6
x8=a*(x7-x6)+x7
x9=a*(x8-x7)+x8
x10=a*(x9-x8)+x9

print(x1)
print(x2)
print(x3)
print(x4)
print(x5)
print(x6)
print(x7)
print(x8)
print(x9)
print(x10)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String W  = br.readLine().toLowerCase();
        String T;
        int count = 0;
        while(!(T=br.readLine()).equals("END_OF_TEXT")){
        	String TList[] = T.toLowerCase().split(" ");
        	for(int i=0;i<TList.length;i++){
        		if(TList[i].equals(W)){
        			count++;
        		}
        	}

        }
        System.out.println(count);
    }
}

Measured memory_bytes: 24220
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
  cin>>a>>b>>c;
  if(a>b){
   int tmp=a;
    a=b;
    b=tmp;
  }
  if(a<c&&c<b)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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

int main() {
    int64_t A, B, K;
    cin >> A >> B >> K;

  	if(A > 0){
      if(K > A){
        K -= A;
        A = 0;
      }else{
        A -= K;
        K = 0;
      }
    }
  	if(B > 0){
      if(K > B){
        K -= B;
        B = 0;
      }else{
        B -= K;
        K = 0;
      }
    }
        
    cout << A << " " << B << endl;
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
g = [[] for i in range(n)]
for i in range(m):
    a,b = na()
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

from collections import deque
d = deque([0])
dp = [100000000000]*n
ma = [0]*n
i = 1

while d:
    a = d.popleft()
    for j in g[a]:
        if dp[j] > i:
            dp[j] = i
            ma[j] = a
            d.append(j)
    i += 1

print('Yes')

for i in range(1,n):
    print(ma[i]+1)

Measured memory_bytes: 35800
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[3005][3005];
ll solve(ll arr[],int i,int j){
    if(j<i)
        return 0;

    if(dp[i][j]!=-1)
        return dp[i][j];
    
    
    return dp[i][j] = max(arr[i] + min(solve(arr,i+2,j),solve(arr,i+1,j-1)),arr[j]+min(solve(arr,i+1,j-1),solve(arr,i,j-2)));
}
int main()
{
    int n;
    cin>>n;
    memset(dp,-1,sizeof dp);
    ll arr[n];
    ll sum =0;
    for(int i=0;i<n;i++)
        cin>>arr[i],sum+=arr[i];
    
   // cout<<solve(arr,0,n-1)<<endl;
    cout<<2*solve(arr,0,n-1)-sum;
    
    return 0;
}

Measured memory_bytes: 74252
use std::cmp::min;

fn main() {
    let buf = io::read_string();
    let mut sc = io::Scanner::new(&buf);

    let n: usize = sc.read();
    let k: usize = sc.read();
    let xs: Vec<i64> = sc.read_vec(n);
    let mut res = <i64>::max_value();

    for l in 0..(n - k + 1) {
        let r = l + k - 1;

        res = min(res, xs[r].abs() + (xs[r] - xs[l]).abs());
        res = min(res, xs[l].abs() + (xs[r] - xs[l]).abs());
    }

    println!("{}", res);
}

#[allow(dead_code)]
mod io {
    use std;
    use std::io::Read;
    use std::str::{FromStr, SplitWhitespace};
    pub struct Scanner<'a> {
        iter: SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }
        pub fn read<T: FromStr>(&mut self) -> T {
            self.iter
                .next()
                .unwrap()
                .parse()
                .ok()
                .expect("parsing failed")
        }
        pub fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.read()).collect()
        }
    }
    pub fn read_string() -> String {
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }
}


Measured memory_bytes: 6396
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush


def solve():
    N, M = MI()

    ans = 1
    for i in range(1, int(pow(M, 0.5))+1):
        if M % i: continue
        j = M // i

        if i * N <= M: ans = max(ans, i)
        if j * N <= M: ans = max(ans, j)
    print(ans)




if __name__ == '__main__':
    solve()


Measured memory_bytes: 3444
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<queue>

using namespace std;

using lli = long long int;
using ulli = unsigned long long int;

//#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

lli A ,B;

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

	cin >> A >> B;
	if(A%3 == 0 || B % 3 == 0 || (A+B) % 3 == 0){
		cout << "Possible\n";
	}else{
		cout << "Impossible\n";
	}
  return 0;
}


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

int main() {
  string S;
  
  cin >> S;
  
  if(S.at(0) == S.at(1) || S.at(1) == S.at(2) || S.at(2) == S.at(3)){
    cout << "Bad" << endl;
  } else {
    cout << "Good" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
int main(){
int a,b;
std::cin >> a >> b ;
if (a<b){
std::cout << "a" <<" < "<< "b" <<"\n";
}else if(a>b){
std::cout << "a" <<" > "<< "b" <<"\n";}
else
{std::cout << "a" <<" == "<< "b" <<"\n";}

return 0;
}

Measured memory_bytes: 3068
# include <bits/stdc++.h>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007

using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) x *= i;
    return x;
}


int main(){
    ll n;
    cin>>n;
    map<string,ll> mp;
    rep(i,n){
        string s;
        cin>>s;
        mp[s]++;
    }
    ll maxi=0;
    for(auto p : mp) maxi=max(maxi,p.second);
    for(auto p : mp) if(p.second==maxi) cout<<p.first<<endl;
    return 0;
}

Measured memory_bytes: 25216
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
int n,k;cin>>n>>k;
int dp[n];
int h[n];
int x;
int  mind=1e10+24;
for(int i=0;i<n;i++){
    cin>>h[i];
}
dp[0]=0;
for(int i=1;i<n;i++){
    for(int j=k;j>0;j--){
        if(i-j>=0){
            x=h[i]-h[i-j];
            mind=min(mind,dp[i-j]+abs(x));
        }
    }
    dp[i]=mind;
    mind=1e10+24;
}
cout<<dp[n-1];
return 0;
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public int X, Y;

        public void Run()
        {
            {
                var line = Input.ReadIntArray();
                X = line[0];
                Y = line[1];
            }

            int ret = int.MaxValue;

            if (Y >= X) ret = Math.Min(ret, Y - X);
            if ((-Y) >= X) ret = Math.Min(ret, (-Y - X) + 1); // 1.. -> Reverse
            if(Y >= (-X)) ret = Math.Min(ret, (Y - (-X)) + 1); // Reverse -> 1..
            if ((-Y) >= (-X)) ret = Math.Min(ret, ((-Y) - (-X)) + 2); // Reverse -> 1.. -> Reverse
            Console.WriteLine(ret);
        
        }
    }

    // libs ----------


    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }

    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Measured memory_bytes: 13396