akhauriyash/Code-Regression huggingface dataset:
/*input
akasaka

*/
 
/*
                                                    ______________
                                                          |       )
                                                          |   )   /
                                                          |______/
                                                    |     |      \
                                                    |     |   )   \
                                                    |_____|_______)
 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;
 
#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
 
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
  int x = 1 % mod;
  while(b){
    if(b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

bool isPalin(string str) {
  int n = str.size();
  for (int i = 0; i < n / 2; i++) {
    if (str[i] != str[n - i - 1]) return false;
  }
  return true;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  string str;
  cin >> str;
  int n = str.size();
  bool ok = isPalin(str);
  ok &= isPalin(str.substr(0, n / 2));
  ok &= isPalin(str.substr((n + 3) / 2 - 1, n));
  cout << (ok ? "Yes" : "No") << endl;

  return 0;
}

Measured memory_bytes: 256
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
INF = float("inf")

n = int(input())
F =[list(map(int,input().split())) for i in range(n)]
P =[list(map(int,input().split())) for i in range(n)]

ans = -INF
for i in range(1,1024):
    profit = 0
    for j in range(n):
        cnt = 0
        for x in range(10):
            if (i >> x) %2 == 1 and F[j][x] == 1:
                cnt += 1
        profit += P[j][cnt]
    ans = max(ans,profit)
print(ans) 

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

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  bool res = false;
  for(int i=0; i<100; ++i){
    for(int j=0; j<100; ++j){
      if(a*i + a*j % b == c)
        res = true;
    }
  }
  if(res) cout << "YES" << endl;
  else cout << "NO" << endl;
}
  

Measured memory_bytes: 256
use proconio::input;
use std::cmp::{min, Reverse};
use std::collections::BinaryHeap;

struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<i32>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            parent: (0..n).map(|i| i).collect(),
            rank: vec![0; n],
        }
    }

    fn find(&mut self, n: usize) -> usize {
        if self.parent[n] == n {
            return n;
        };
        self.parent[n] = self.find(self.parent[n]);
        self.parent[n]
    }

    fn same(&mut self, n: usize, m: usize) -> bool {
        self.find(n) == self.find(m)
    }

    fn unit(&mut self, n: usize, m: usize) {
        let n = self.find(n);
        let m = self.find(m);
        if n == m {
            return;
        }
        if self.rank[n] > self.rank[m] {
            self.parent[m] = n;
        } else {
            self.parent[n] = m;
            if self.rank[n] == self.rank[m] {
                self.rank[n] += self.rank[m];
            }
        }
    }
}

fn main()
{
    input! {
    n:usize,
    mut g:[(i64,i64);n],
    }
    let mut uf = UnionFind::new(n);
    let mut v = Vec::new();
    for (i, &(a, b)) in g.iter().enumerate() {
        v.push((a, b, i));
    }
    v.sort();
    let mut q = BinaryHeap::new();
    for i in 0..v.len() - 1 {
        let (a, b) = (v[i].2, v[i + 1].2);
        let (x0, y0) = (v[i].0, v[i].1);
        let (x1, y1) = (v[i + 1].0, v[i + 1].1);
        let dist = min((x0 - x1).abs(), (y0 - y1).abs());
        q.push(Reverse((dist, a, b)));
    }
    v.sort_by(|(_, y0, _), (_, y1, _)| y0.cmp(y1));
    for i in 0..v.len() - 1 {
        let (a, b) = (v[i].2, v[i + 1].2);
        let (x0, y0) = (v[i].0, v[i].1);
        let (x1, y1) = (v[i + 1].0, v[i + 1].1);
        let dist = min((x0 - x1).abs(), (y0 - y1).abs());
        q.push(Reverse((dist, a, b)));
    }

    let mut ans = 0;

    while let Some(Reverse((d, a, b))) = q.pop() {
        if uf.same(a, b) {
            continue;
        }
        uf.unit(a, b);
        ans += d;
    }

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

Measured memory_bytes: 14744
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5+11;
typedef long long ll;
ll f[N],h[N];
int main()
{
    memset(f,0x3f,sizeof f);
    int n,k;scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;++i)   scanf("%lld",&h[i]);
    f[1] = 0;
    for(int i = 1;i <= n;++i)
        for(int j = i - 1;j >= i - k && j >= 1;--j)
            f[i] = min(f[j] + abs(h[i] - h[j]),f[i]);
    cout << f[n];
    return 0;
}


Measured memory_bytes: 1920
n=int(input())
A=list(map(int,input().split()))

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(j) for j in  bin(A[i])[2:]]
    B[i]= [0]*(20-len(B[i]))+B[i]

ans=n
#累積和
R=[[] for i in range(n+1)]
R[0]=[0]*20
for i in range(n):
    R[i+1] = [l+k for l,k in zip(R[i], B[i])]
###

#転置
TR=[[0]*(n+1) for i in range(20)]
for i in range(n+1):
    for j in range(20):
        TR[j][i]=R[i][j]

from bisect import bisect_left as bi
for i in range(n,1,-1):
    now=R[i] ; #print(now)
    # score=
    ans+=i-max([bi(TR[k],now[k]-1) for k in range(20)])-1
    #print(ans)

print(ans)


Measured memory_bytes: 244308
N = int(input())
h = list(map(int, input().split()))
costs = [0] * N

costs[0] = 0
costs[1] = abs(h[1] - h[0])

for i in range(2, N):
  one = costs[i-1] + abs(h[i] - h[i-1])
  two = costs[i-2] + abs(h[i] - h[i-2])
  costs[i] = min(one, two)

print(costs[N-1])


Measured memory_bytes: 84688
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp(a, b) make_pair(a, b)
#define pb(t) push_back(t)
#define ft first
#define sc second
#define pt(num) cout << num << "\n"
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define chmax(a, b) (a<b ? a=b : 0)
#define chmin(a, b) (a>b ? a=b : 0)
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 101010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;


int main(void) {
    ll N;
    cin >> N;
    ll i;
    ll t=0;
    ll ans=0;
    for(i=0; i<N; i++) {
        ll h;
        cin >> h;
        ans+=max(h-t, 0);
        t=h;
    }
    
    pt(ans);
}




Measured memory_bytes: 256
n = gets.chomp.to_i
a = gets.chomp
b = gets.chomp
c = gets.chomp

count = 0
n.times do |i|
  if a[i] == b[i] && b[i] == c[i]
  elsif a[i] != b[i] && b[i] != c[i] && a[i] != c[i]
    count += 2
  else
    count += 1
  end
end
p count


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

const int MAX = 510000;
const int MOD = 1000000007;
const int MAX_N = 200000;

ll value(int a,int b){
  ll d=10;
  ll sum=0;
  for(int i=0;i<b;i++){
  //  cout << sum << endl;
    sum = d*sum + a;
  }
  return sum;
}

int main(int argc, const char * argv[]) {
  int a,b;cin >> a >> b;
  ll a_sum = value(a,b);
  ll b_sum = value(b,a);
  cout << max(a_sum,b_sum) << endl;

   return 0;
}


Measured memory_bytes: 256
s = input()
t = input()
ans = len(t)
c = 0
for i in range(len(s)-len(t)+1):
  c = 0
  for j in range(len(t)):
    if s[i+j] != t[j]:
      c += 1
  if ans > c:
    ans = c
print(ans)



Measured memory_bytes: 8988
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <queue>

using namespace std;

constexpr int inf = 1e9+7;

vector<long long> fac(1000001);
vector<long long> ifac(1000001);

long long mpow(long long _x, long long _n) {
    long long ans = 1;
    while (_n != 0) {
        if (_n & 1) ans = ans * _x % inf;
        _x = _x * _x % inf;
        _n = _n >> 1;
    }
    return ans;
}

long long dupc(long long _a, long long _b) {
    if (_a == 0 && _b == 0) return 1;
    if (_a < 0 || _b == 0) return 0;
    long long tmp = ifac[_a-1] * ifac[_b] % inf;
    return tmp * fac[_a + _b - 1] % inf;
}

int main () {
    fac[0] = 1;
    ifac[0] = 1;
    for (long long i = 0; i < 1000000; i++) {
        fac[i+1] = fac[i] * (i+1) % inf;
        ifac[i+1] = ifac[i] * mpow(i+1, inf-2) % inf;
    }

    long long  N, M;
    cin>>N>>M;

    long long result = 1;
    for (long long i = 2; i < 1000000000; i++) {
        int count = 0;
        while (M % i == 0) {
            M /= i;
            count++;
        }
        if (count > 0) result = result * dupc(N, count) % inf;
        if (M == 1) break;
    }

    cout<<result<<endl;

    return 0;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
int a[10005];
int main(){
	int n;long long s=0;cin>>n;
	for(int i=0;i<n;i++)cin>>a[i],s+=a[i];
	sort(a,a+n);
	printf("%d %d %lld\n",a[0],a[n-1],s);
	return 0;
}


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

int main(){
  long long N, D;
  long long x, y;
  int counter = 0;
  cin >> N >> D;
  for (long long i = 0; i < N; i++){
      cin >> x >> y;
      long long res = x*x + y*y; 
      if (sqrt(res) <= D) counter++;
  }
  cout << counter << endl;
return 0;
}

Measured memory_bytes: 3648
def run_length(data, init=''):
    length = []
    tmp = init
    cnt = 0
    for c in data:
        if tmp != c:
            length.append(cnt)
            cnt = 0
        tmp = c
        cnt += 1
    length.append(cnt)
    return length


def resolve():
    s = input()
    if s[0] != '<':
        s = '<' + s
    if s[-1] != '>':
        s = s + '>'

    array = run_length(s)
    ans = 0
    for i in range(1, len(array), 2):
        a,b = array[i], array[i+1]
        mn = min(a,b) - 1
        mx = max(a,b)
        ans += (mn+1) * (mn) // 2 + mx * (mx+1) // 2
    #     print(a,b, (mn+1) * (mn) // 2 + mx * (mx+1) // 2)
    # print(array)
    print(ans)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 11860
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, n) for (int i = 1; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
int main()
{
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;

    int maxWater = 100 * A, maxSuger = 0;
    double maxV = -1;
    rep(b, 31) {
        int water = 100 * B * b;
        if (water > F) {
            continue;
        }
        rep(a, 31) {
            water = 100 * B * b + 100 * A * a;
            if (water > F) {
                continue;
            }
            if (water <= 0) {
                continue; 
            }

            for (int d = 0; d * D + water <= F; d++) {
                for (int c = 0; c * C + water <= F; c++) {
                    int suger = c * C + d * D;
                    if (suger <= 0 || water + suger > F || suger > water / 100 * E) {
                        continue;
                    }
                    double v = (double)suger / (suger + water);
                    if (maxV < v) {
                        maxWater = water;
                        maxSuger = suger;
                        maxV = v;
                    }

                }
            }

            // // 3000以下
            // int maxS = water * E / 100;
            // rep(d, maxS / D + 1) {
            //     if (maxS - d * D < 0) {
            //         continue;
            //     }
            //     int c = (maxS - d * D) / C;
            //     int suger = c * C + d * D;
            //     if (suger <= 0 || water + suger > F || suger > water / 100 * E) {
            //         continue;
            //     }
            //     double v = (double)suger / (suger + water);
            //     if (maxV < v) {
            //         maxWater = water;
            //         maxSuger = suger;
            //         maxV = v;
            //     }
            // }
        }
    }

    cout << (maxWater + maxSuger) << " " << maxSuger << endl;
    

    return 0;
}

Measured memory_bytes: 3564
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#define FOR(i,a,b) for (int i=(a),for_##i##_max=(b);i<=(for_##i##_max);++i)
#define RFOR(i,a,b) for (int i=(a),rfor_##i##_min=(b);i>=(rfor_##i##_min);--i)
#define REP(i,n) for (int i=0,rep_##i##_len=(n);i<(rep_##i##_len);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

namespace { // Basics

template<typename T>
void chmin(T &x, T y) {
  x = std::min(x, y);
}

template<typename T>
void chmax(T &x, T y) {
  x = std::max(x, y);
}

template<typename T>
__attribute__((unused))
const auto minimum = static_cast<T const &(*)(T const &, T const &)>(std::min);

template<typename T>
__attribute__((unused))
const auto maximum = static_cast<T const &(*)(T const &, T const &)>(std::max);

template<typename T>
__attribute__((unused))
T constexpr infty = std::numeric_limits<T>::max / 3;
template<>
__attribute__((unused))
auto constexpr infty<int> = 1'100'100'100;
template<>
__attribute__((unused))
auto constexpr infty<long long int> = 100'500'400'300'200'100LL;

using lli = long long int;
using ld = long double;

} // namespace

using namespace std;

int main() {
  // cout << fixed << setprecision(10);

  int A; string S;
  cin >> A >> S;
  cout << (A >= 3200 ? S : "red") << "\n";
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // ABC155B - Papers, Please

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];

        String ans = "APPROVED";
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            if (a[i] % 2 == 0) {
                if (a[i] % 3 == 0 || a[i] % 5 == 0) {

                } else {
                    ans = "DENIED";
                }
            }
        }

        System.out.println(ans);
    }
}

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

int a[1000010];
int pa = 0;

int f(int n) {
	if (n % 2 == 0) return n / 2;
	else return 3*n + 1;
}

bool inside(int x) {
	for (int i = 0; i < pa - 1; i++) {
		if (x == a[i]) return true;
	}
	return false;
}

int main() {
	cin >> a[pa];
	for (pa = 1; pa < 1000010; pa++) {
		a[pa] = f(a[pa - 1]);
		if (inside(a[pa])) {
			cout << pa + 1 << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
l = [list(map(int, input().split())) for _ in range(3)]
#print(l)
n = int(input())
bingo = [int(input()) for _ in range(n)]
#print(bingo)

for i in range(3):
    for j in range(3):
        if l[i][j] in bingo:
            l[i].pop(j)
            l[i].insert(j,0)
#print(l)

if len(set(l[0])) == 1 or len(set(l[1])) == 1 or len(set(l[2])) == 1:
    print('Yes')
    exit()

if l[0][0] == l[1][0] == l[2][0] or l[0][1] == l[1][1] == l[2][1] or l[0][2] == l[1][2] == l[2][2]:
    print('Yes')
    exit()

if l[0][0] == l[1][1] == l[2][2] or l[0][2] == l[1][1] == l[2][0]:
    print('Yes')
    exit()
    
print('No')




Measured memory_bytes: 3064
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
        checked {
#if DEBUG
            MyDebugger.Test(process, "../TextFile1.txt");
            //TestCaseMaker.MakeTestCase1("../TextFile2.txt");
            //MyDebugger.Test(process, "../TextFile2.txt");
#else
            object ret = process(new StreamReader(Console.OpenStandardInput()));
            Console.WriteLine(ret);
#endif
        }
    }

    static object process(TextReader input) {
        var spl = input.ReadLine().Split(' ');
        var n = int.Parse(spl[0]);
        var x = int.Parse(spl[1]);
        var t = int.Parse(spl[2]);

        var co = n/x;
        if(n % x != 0) co++;

        return co * t;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


Measured memory_bytes: 27376
import java.util.Scanner;
//import java.io.*;
//import java.util.Arrays;
public class Main {
	public static void main(String[] args) throws java.io.IOException {
		Scanner scan = new Scanner(System.in);
		//InputStreamReader is = new InputStreamReader(System.in);
		//BufferedReader br = new BufferedReader(is);
		//String text = scan.next();
		Main mySystem = new Main();
		while(scan.hasNext()){
			int cnt = 0;
			int sima[][] = new int[12][12];
			for(int i = 0 ; i < 12 ; i++){
				String mozi = scan.next();
				char[] a = mozi.toCharArray();
				int ch[] = new int[12];
				for(int j = 0 ; j < 12 ; j++){
					ch[j] = Integer.parseInt("" + a[j]); 
					sima[i][j] = ch[j];
				}
			}
			for(int i = 0 ; i < 12 ; i++){
				for(int j = 0 ; j < 12 ; j++){
					if(sima[i][j] == 1){
						mySystem.Simahantei(i,j,sima);
						cnt++;
					}
				}
			}
			System.out.println(cnt);
		}
	}
	public void Simahantei(int w , int h ,int sima[][]){
		sima[w][h] = 0;
		if(w+1 < 12){
			if(sima[w+1][h] == 1){
				Simahantei(w+1 , h , sima);
			}
		}
		if(h+1 < 12){
			if(sima[w][h+1] == 1){
				Simahantei(w , h+1 , sima);
			}
		}
		if(w-1 > -1){
			if(sima[w-1][h] == 1){
				Simahantei(w-1 , h , sima);
			}
		}
		if(h-1 > -1){
			if(sima[w][h-1] == 1){
				Simahantei(w , h-1 , sima);
			}
		}
	}
}

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

const int MAX = 200000;
int main() {
	static int N, A[MAX];
	cin >> N;
	for (int i = 0;i < N;i ++) cin >> A[i];
	
	static int64_t sum[MAX + 1]; // 累積和
	sum[0] = 0;
	for (int i = 0;i < N;i ++) sum[i + 1] = A[i] + sum[i];
	sort(sum, sum+N+1);
	int64_t ans = 0;
	int num = 1;
	for (int i = 1;i <= N;i ++) {
		if (sum[i] == sum[i - 1]) num ++; // 累積和が同値になるものの個数
		else {
			ans += (int64_t)num * (num - 1) / 2; // 総和が0になる区間の数
			num = 1;
		}
	}
	ans += (int64_t)num * (num - 1) / 2;
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

まず、連続する～と総和～と来た場合は累積和を作りましょう。それで大きく話が変わるから。
ここで、1からxの区間の総和をsum[x]とするよ
この時、ある区間i～jの総和が0であることは、sum[j]-sum[i+1]=0、つまりsum[j]=sum[i+1]と言えるよね
つまり、sum[x]が同値になるようなx同士でしか総和は0にならないし、逆に同値になるようなx同士から任意の2個を選んで良い訳だ
ここで、もしk個が同値になるとして、その中から2個を選ぶ方法はk(k-1)/2通りあるよ
後は一度ソートしておくと左から順に確認できるので、O(NlogN)で解けるよ
*/

Measured memory_bytes: 2560
n = int(input())
h = list(map(int, input().split()))
cnt = 0
for i in range(1,101):
    now = 0
    for j in range(n):
        if (h[j]>=i):
            if (now == 0):
                cnt += 1
                now = 1
        else:
            now = 0
print(cnt)


Measured memory_bytes: 3060
from typing import List
import sys


def read_data(file_name: str, std_in=True):
    satisfactions_list = list()
    file = sys.stdin if std_in else open(file_name, 'r')
    days = int(file.readline().rstrip())
    satisfaction_decreases = [int(c) for c in file.readline().rstrip().split(" ")]
    for i in range(days):
        satisfactions_list.append([int(c) for c in file.readline().rstrip().split(" ")])
    if not std_in:
        file.close()
    return days, satisfaction_decreases, satisfactions_list


class Contest:
    def __init__(self, _type: int, satisfactions: List[int], satisfaction_decrease: int):
        self.dissatisfaction = 0
        self.type = _type
        self.satisfactions = satisfactions
        self.satisfaction_decrease = satisfaction_decrease

    def __getitem__(self, key: int):
        return self.satisfactions[key - 1]

    def __str__(self):
        return str(self.type)

    def __repr__(self):
        return f"Contest(_type={self.type}, satisfactions={self.satisfactions}, satisfaction_decrease={self.satisfaction_decrease})"

    def heuristic(self, day):
        # return self[day] - 2*(self.dissatisfaction - self.satisfaction_decrease)
        return self[day] - 2*self.dissatisfaction

    def winner(self):
        self.dissatisfaction = 0

    def loser(self):
        self.dissatisfaction -= self.satisfaction_decrease


def get_best(contests: List[Contest], day: int):
    # improve this by optimistically making everyone a loser and then going back to undo that for the winner
    best = contests[0]
    for contest in contests:
        if contest.heuristic(day) > best.heuristic(day):
            best = contest
    return best


def main(file_name="input.txt"):
    contests = list()
    days, satisfaction_decreases, satisfactions_list = read_data(file_name)
    picks = list()

    for (_type, (satisfactions, satisfaction_decrease)) in enumerate(zip(zip(*satisfactions_list), satisfaction_decreases), start=1):
        contests.append(Contest(_type, satisfactions, satisfaction_decrease))

    for day in range(days):
        best = get_best(contests, day + 1)
        for contest in contests:
            if contest.type == best.type:
                contest.winner()
                picks.append(contest)
            else:
                contest.loser()

    return "\n".join([str(pick) for pick in picks])


if __name__ == "__main__":
    print(main("input.txt"))


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

class Main{
    public static void main(String[] args){
        solve();
    }

    public static void solve(){
        Scanner sc = new Scanner(System.in);
 		long a = sc.nextLong();
 		long b = sc.nextLong();
 		long c = sc.nextLong();
 		long d = sc.nextLong();
 		long count = 0;

 		count = b - a + 1;
 		count -= (b / c) - (a / c);
 		count -= (b / d) - (a / d);
 		if(b >= c && a % c == 0){
 			count -= 1;
 		}
 		if(b >= d && a % d == 0){
 			count -= 1;
 		}
 		long e = c;
 		long f = d;
 		if(f<e){
 			long temp = f;
 			f = e;
 			e = temp;
 		}
 		while(true){
 			if(e == 0){
 				break;
 			}
 			long x = f % e;
 			f = e;
 			e = x;
 		}
 		count += (b / (c * d / f)) - (a / (c * d / f));
 		if(b >= (c * d / f) && a % (c * d / f) == 0){
 			count += 1;
 		}

 		System.out.println(count);       
    }
}

Measured memory_bytes: 23764
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<vector>
#include<fstream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<typeinfo>

using namespace std;
#define REP(i,m,n) for(int i=m;i<n;++i)
#define REPll(i,m,n) for(ll i=m;i<n;++i)
#define INF 10000000000000000
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define all(v) v.begin(),v.end()

vector<ll>v;

int main() {
	int n, m, c;
	cin >> n >> m >> c;
	int ans = 0;
	int tmp;
	REP(i, 0, m) {
		cin >> tmp;
		v.push_back(tmp);
	}
	REP(i, 0, n) {
		int hoge = 0;
		REP(j, 0, m) {
			cin >> tmp;
			hoge += tmp * v[j];
		}
		hoge += c;
		if (hoge > 0) {
			ans++;
		}
	}
	cout << ans << endl;
}

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

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef long long ll;
typedef pair<long long, long long> l4;
typedef vector<long long> vll;
typedef double db;
typedef vector<double> vdb;
typedef pair<double, double> dd;
typedef set<int> si;
typedef set<long long> sll;
#define fi first
#define se second
#define matrix(a) vector< vector<a> >
#define sz(a) int((a).size()) 
#define lop(i,a,b) for (int i=a; i<=b; i++)
#define vlop(i,v) lop(i,0,sz(v)-1)
#define vlop1(i,v) lop(i,1,sz(v)-1)
#define rlop(i,a,b) for (int i=b; i>=a; i--)
#define vrlop(i,v) rlop(i,0,sz(v)-1)
#define vrlop1(i,v) rlop(i,1,sz(v)-1)
#define printv(i,v) vlop(i,v)cout<<v[i]<<" "
#define printv1(i,v) vlop1(i,v)cout<<v[i]<<" "
#define all(s) (s).begin(),(s).end()
#define pb push_back
#define enter cout<<'\n'
#define lb(i,v) int(lower_bound(all(v),i)-v.begin())
#define ub(i,v) int(upper_bound(all(v),i)-v.begin())

void dfs(matrix(int)& alist,  int root, vi& visited,vi& d) {
	visited[root] = 1;
	vlop(i, alist[root]) {
		if (!visited[alist[root][i]]) {
			d[alist[root][i]] = d[root] + 1;
			dfs(alist,alist[root][i], visited,d);
		}
	}
	return;
}

int main() {
	int n,u,v;
	cin>>n;
	matrix(int) alist(n+1);
	lop(i,1,n-1){
		cin>>u>>v;
		alist[u].pb(v);
		alist[v].pb(u);
	}
	vi visited(n+1,0),d1(n+1,0),d2(n+1,0);
	dfs(alist,1,visited,d1);
	vlop(i,visited)visited[i]=0;
	dfs(alist,n,visited,d2);
	int fennec=0,snuke=0;
	vlop1(i,d1){
		if(d1[i]<=d2[i])fennec++;
		else snuke++;
	}
	if(fennec>snuke)cout<<"Fennec";
	else cout<<"Snuke";
	return 0;
}

Measured memory_bytes: 13184
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int n, m;
vint edge[100005];
vint ans;

void bfs(int v) {
    queue<int> q;
    q.push(v);
    while(!q.empty()) {
        // show(q.size());
        int p = q.front(); q.pop();
        for (int u : edge[p]) {
            if (ans[u] != -1) continue;
            ans[u] = p;
            q.push(u);
        }
    }
}

int main() {
    cin >> n >> m;
    ans.resize(n, -1);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }

    ans[0] = 0;
    bfs(0);
    // show_ary(ans);
    rep(i, n) {
        if (ans[i] == -1) {
            puts("No");
            return 0;
        }
    }

    puts("Yes");
    srep(i, 1, n) {
        cout << ans[i]+1 << endl;
    }

    return 0;
}

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

int main(){
  int x;
  cin >> x;
  int res = 1;
  for(int i = 2;i<=x;i++) {
    int j = i;
    while (j <= x) {
      j = j*i;
      if(j <= x && res < j){
        res = j;
      }
    }
  }
  cout << res << endl;
}
      
    
    

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

int main(){
  ll n,i,j,k,x,y;
  cin >> n;
  ll a[10001]={0};
  for(i=1;i<=100;i++){
    for(j=i;j<=100;j++){
      for(k=j;k<=100;k++){
        x=i*i+j*j+k*k+i*j+j*k+k*i;
        if((i!=j)&&(j!=k)&&(k!=i)){
          y=6;
        }
        else if((i==j)&&(j==k)){
          y=1;
        }
        else{
          y=3;
        }
        if(x<=10000){
          a[x]+=y;
        }
      }
    }
  }
  for(i=1;i<=n;i++){
    cout << a[i] << endl;
  }
}

Measured memory_bytes: 3624
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    int h,w;
    while(scanf("%d%d",&h,&w)!=EOF)
    {
        char grid[100][100]={0};
        int ans[100][100]={0};//if==-1 (#)
        memset(ans,-1,sizeof(ans));

        for(int i=0;i<h;i++)scanf("%s",grid[i]);

        for(int i=0;i<h;i++)
        {
            for(int j=0;j<w;j++)
            {
                if(grid[i][j]=='.')
                {
                    ans[i][j]=0;
                    if(i-1>=0 && j-1>=0)if(grid[i-1][j-1]=='#')ans[i][j]++;

                    if(i-1>=0 && j>=0)if(grid[i-1][j]=='#')ans[i][j]++;

                    if(i-1>=0 && j+1<w)if(grid[i-1][j+1]=='#')ans[i][j]++;

                    if(i>=0 && j-1>=0)if(grid[i][j-1]=='#')ans[i][j]++;

                    if(i>=0&& j+1<w)if(grid[i][j+1]=='#')ans[i][j]++;

                    if(i+1<h && j-1>=0)if(grid[i+1][j-1]=='#')ans[i][j]++;

                    if(i+1<h &&j>=0)if(grid[i+1][j]=='#')ans[i][j]++;

                    if(i+1<h && j+1<w)if(grid[i+1][j+1]=='#')ans[i][j]++;
                }
            }
        }

        for(int i=0;i<h;i++)
        {
            for(int j=0;j<w;j++)
            {
                if(ans[i][j]==-1)printf("#");
                else printf("%d",ans[i][j]);
            }
            printf("\n");
        }
    }
}


Measured memory_bytes: 256
def dir2num(str)
  case str
  when 'N' then [0, 1]
  when 'E' then [1, 0]
  when 'S' then [0, -1]
  when 'W' then [-1, 0]
  end
end

def move_robot(arr)
  $r.each do |arr|
    arr[1].to_i.times do
      $moved_pos << $pos = $pos.zip(dir2num(arr[0])).map{ |a| a.inject(:+) }
    end
  end
end
a = []
while line = gets
  break if line.to_i == 0
  h_num = line.to_i
  $pos = [10, 10]
  $h_pos = []
  $moved_pos = []
  h_num.times do
    $h_pos << gets.split.map(&:to_i)
  end
  r_num = gets.to_i
  $r = []
  r_num.times do
    $r << gets.split
  end

  move_robot($r)
  puts ($h_pos - $moved_pos).none? ? "Yes" : "No"
end

Measured memory_bytes: 6112
/*
 * 
 * Author: Pranav Bansal
 * 
*/
#include<bits/stdc++.h>

#define int long long
#define fast ios_base::sync_with_stdio(false); cin.tie(0);
#define rep(i,a,n) for(int i=a;i<n;i++)
#define all(x) x.begin(),x.end()
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define UMP(x,y) unordered_map<x,y>
#define MP(x,y) map<x,y>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define inf 1e18
#define endl "\n"
#define coutd(n) cout << fixed << setprecision(n)
#define watch(x) cout<<#x<<" = "<<x<<endl;
typedef double db;
typedef long double ld;	
const int mod = 1000000007;

using namespace std;

int32_t main(){
    fast
    	
    //int t;
	//cin>>t;
	//rep(_,0,t){
		
	//}	
	ld a,b;
	cin>>a>>b;
	
	cout<<(int)(a*b);
    return 0;
}


Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
int main ()
{
    int N,T,A;
    long H[1010];
    int tmp;
    long sa=10000000;
    cin >> N >> T >> A;
    int ans;
    for(int i=0;i<N;i++){
        cin >> tmp;
        H[i]=1000*T-tmp*6;
        if(abs(1000*A-H[i])<sa){
            ans=i+1;
            sa=abs(1000*A-H[i]);
        }
    }
    cout << ans << endl;
   return 0;
}












Measured memory_bytes: 256
# -*- coding: utf-8 -*-
#ABC138C
import copy
import sys
import math

n = int(input())
tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))

hoge.sort()

total=hoge[0]
for i in range(1,n):
	total+=hoge[i]
	total/=2

print(total)



Measured memory_bytes: 3572
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int main() {
	int n; cin >> n;
	long int l[90];
	l[0] = 2;
	l[1] = 1;
	for(int i=2;i<=n;i++){
		l[i] = l[i-1] + l[i-2]; 
	}
	cout << l[n] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	char in[201], tmp[201];
	int m, n, i, j;

	while (1) {
		scanf("%200s ", in);
		if (in[0] == '-')
			break;

		scanf("%d ", &m);
		while (m--) {
			scanf("%d ", &n);
			for (i = 0; in[i+n] != '\0'; i++) {
				tmp[i] = in[i+n];
			}
			for (j = 0; j < n; j++) {
				tmp[i+j] = in[j];
			}
			tmp[i+j] = '\0';
			for (i = 0; tmp[i] != '\0'; i++) {
				in[i] = tmp[i];
			}
		}
		puts(in);
	}
	return 0;
}

Measured memory_bytes: 588
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  string s,t;
  cin>>s>>t;
  ll ans=0;
  for(int i=0;i<s.size();i++){
    if(s[i]!=t[i]){
      ans++;
    }
  }
  cout<<ans<<endl;
  
}

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

public class Main {
	FastScanner in = new FastScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);

	public void run() {
		int n = in.nextInt() - 1;
		
		int res = 0;
		while (n > 0) {
			n /= 3;
			res++;
		}
		System.out.println(res);
		out.close();
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();

			return array;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();

			return array;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();

			return array;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}

Measured memory_bytes: 17008
K,N=map(int,input().split())
n=list(map(int,input().split()))
if n[N-1]-n[0] < (K-n[1])+n[0]:
  dist=n[N-1]-n[0]
else:
  dist=(K-n[1])+n[0]
for i in range(1,N-1):
  if dist > (K-n[i-1])+n[i]:
    dist= (K-n[i-1])+n[i]
  if dist > (K-n[i+1])+(n[i]-0):
    dist= (K-n[i+1])+(n[i]-0)
print(dist)

Measured memory_bytes: 26444
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vs = vector<string>;
using vll = vector<long long>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int a, b, q;
    cin >> a >> b >> q;
    vll s(a+2), t(b+2);
    s[0] = t[0] = -1e18;
    s[a+1] = t[b+1] = 1e18; 
    rep(i, a) cin >> s[i+1];
    rep(i, b) cin >> t[i+1];

    while (q--) {
        ll x;
        cin >> x;
        ll ans = __LONG_LONG_MAX__;
        int sidx = lower_bound(s.begin(), s.end(), x) - s.begin();
        int tidx = lower_bound(t.begin(), t.end(), x) - t.begin();
        rep(i, 2) {
            rep(j, 2) {
                chmin(ans, abs(x-s[sidx-i]) + abs(s[sidx-i] - t[tidx-j]));
                chmin(ans, abs(x-t[tidx-j]) + abs(s[sidx-i] - t[tidx-j]));
            }
        } 
        cout << ans << endl;
    }
}

Measured memory_bytes: 2944
s=input()
N=len(s)
table=[]
mod=998244353

if s[0]=="0":
  table.append((2,0))
elif s[0]=="1":
  table.append((1,1))
elif s[0]=="2":
  table.append((0,2))
for i in range(1,N):
  r,b=table[-1]
  if s[i]=="0":
    r,b=table[-1]
    table.append((r+2,b))
  elif s[i]=="1":
    r,b=table[-1]
    table.append((r+1,b+1))
  elif s[i]=="2":
    r,b=table[-1]
    table.append((r,b+2))
for i in range(N):
  table.append(table[-1])
dp=[[0]*(2*N+1) for i in range(2*N+1)]
dp[0][0]=1
for i in range(2*N):
  for k in range(2*N):
    if k+1<=table[i][0]:
      dp[i+1][k+1]=(dp[i+1][k+1]+dp[i][k])%mod
    if i+1-k<=table[i][1]:
      dp[i+1][k]=(dp[i+1][k]+dp[i][k])%mod
ans=0
for k in range(2*N+1):
  ans=(ans+dp[2*N][k])%mod
print(ans)


Measured memory_bytes: 167388
using System;
using System.Collections.Generic;
using System.Linq;

namespace B {
    class Program {
        static void Main (string[] args) {
            var n = int.Parse (Console.ReadLine ());
            var xs = new List<double> ();
            var us = new List<string> ();
            foreach (var i in Enumerable.Range (0, n)) {
                var xu = Console.ReadLine ().Split (' ');
                var x = xu[0];
                var u = xu[1];
                xs.Add (double.Parse (x));
                us.Add (u);
            }

            var fullAmount = 0.0;
            foreach (var i in Enumerable.Range (0, n)) {
                if (us[i] == "JPY") {
                    fullAmount += xs[i];
                } else {
                    var bc2yen = xs[i] * 380000.0;
                    fullAmount += bc2yen;
                }
            }

            Console.WriteLine (fullAmount);
        }
    }
}

Measured memory_bytes: 13268
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

int main(void){
    int n, a; cin >> n >> a;
    cout << n * n - a << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

using pip = pair<int, pii>;

void update(map<pip, lint> &dp, int i, int j, int k, lint x){
    if(dp.find({i, {j, k}}) != dp.end()) chmax(dp[{i, {j, k}}], x);
    else dp[{i, {j, k}}] = x;
}

lint get_val(map<pip, lint> &dp, int i, int j, int k){
    return dp.find({i, {j, k}}) != dp.end() ? dp[{i, {j, k}}] : -INF;
}

int main(){
    int n;
    scanf("%d", &n);
    lint a[n];
    rep(i, n) scanf("%lld", &a[i]);

    map<pip, lint> dp;
    dp[{0, {0, 0}}] = 0;
    rep(i, n)For(j, (i-1)/2, (i-1)/2+2)rep(k, 2){
        lint tmp = get_val(dp, i, j, k);
        update(dp, i+1, j, 0, tmp);
        if(k == 0) update(dp, i+1, j+1, 1, tmp + a[i]);
    }

    lint ans = -INF;
    rep(k, 2) chmax(ans, get_val(dp, n, n/2, k));
    printf("%lld\n", ans);
}

Measured memory_bytes: 55352
H,W = map(int,input().split())

list =''

for i in range(W+2):
	list +='#'
a = [input() for i in range(H)]

print(list)

for j in range(len(a)):
	a[j] ="#"+a[j]+"#"
	print(a[j])
	
print(list)



Measured memory_bytes: 3068
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){for(ll i=0;i<v.size();++i) x<<v[i]<<" ";return x;}
template <typename X> ostream& operator << (ostream& x,const set<X>& v){for(auto it:v) x<<it<<" ";return x;}
template <typename X, typename Y> ostream& operator << (ostream& x, const pair<X,Y>& v) {x<<v.ff<<" "<<v.ss;return x;}
template <typename T, typename S> ostream& operator << (ostream& os, const map<T, S>& v) { for (auto it : v) os << it.first << "=>" << it.second << endl; return os; }
struct pair_hash {inline std::size_t operator()(const std::pair<ll, ll> & v) const {return v.first*31+v.second;}};
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC targett("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define fr first
#define sc second
#define prnt(m) for(auto it = m.begin() ; it != m.end() ; ++it){cout<<*it<<endl;}
#define tra(it,m) for(auto it=m.begin();it!=m.end();++it)
#define DBG(x) cout<<"# # #     "<<x<<'\n';
#define fri(i,s,n) for(ll i=s;i<n;i++)
#define mod 1000000007LL
#define mod2 998244353
#define vct2 vector<vector<ll>>
#define vct vector<ll>
#define pll pair<ll,ll>
#define rz(n) resize(n)
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define arrin(a,n) for(ll i = 0; i < n ; i++){cin>>a[i];}
#define arrout(a,n) for(ll i = 0;i < n; i++){cout<<a[i]<<" ";}
#define ex(s) cout<<s<<endl,exit(0);
#define inf 2e18
#define h_p 1110111110111;
#define five 100005;
#define six 1000005;
#define printclock cerr<<"Time "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
//_______________________________________________________________________________
int main()
{
       ll n;
       cin>>n;
       ll a[n];
       arrin(a,n);
       map<ll,ll> mp;
       ll tot = 0;
       fri(i,0,n)
       {
              tot += mp[-a[i]+i];
              mp[a[i]+i]++;
       }
       cout<<tot<<endl;
}


Measured memory_bytes: 27796
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=100005;
int L[MAXN],R[MAXN],len[MAXN],n;
priority_queue<LL> hp2;
priority_queue<LL,vector<LL>,greater<LL> > hp1;
LL mov1,mov2;
int main()
{
	n=read();
	for(int i=1;i<=n;i++)L[i]=read(),R[i]=read(),len[i]=R[i]-L[i];
	hp1.push(R[1]);
	hp2.push(R[1]);LL ans=0;
	for(int i=2;i<=n;i++)
	{
		mov1+=len[i];mov2-=len[i-1];
		LL fl=hp2.top()+mov2,fr=hp1.top()+mov1;
		if(fl<=R[i]&&R[i]<=fr)hp1.push(R[i]-mov1),hp2.push(R[i]-mov2);
		else if(fl<=R[i])
		{
			ans+=R[i]-fr;hp1.pop();hp2.push(fr-mov2);
			hp1.push(R[i]-mov1);hp1.push(R[i]-mov1);
		}
		else if(R[i]<=fr)
		{
			ans+=fl-R[i];hp2.pop();hp1.push(fl-mov1);
			hp2.push(R[i]-mov2);hp2.push(R[i]-mov2);
		}
	}pr2(ans);
	return 0;
}



Measured memory_bytes: 3188