akhauriyash/Code-Regression huggingface dataset:
// -*- coding: utf-8 -*-
//import java.awt.*;
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    InputStream inputStream;
    if (args.length > 0 && args[0].equals("devTesting")) {
      try {
        inputStream = new FileInputStream(args[1]);
      } catch(FileNotFoundException e) {
        throw new RuntimeException(e);
      }
    } else {
      inputStream = System.in;
    }
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    TaskB solver = new TaskB();
    solver.solve(1, in, out);
    out.close();
  }
  
  static class TaskB {    
    long x, n;
    long[] a;
    
    void solve(int testNumber, InputReader in, PrintWriter out) {
      n = in.nextInt();        
      x = in.nextInt();
      a = new long[(int) n];
      for (int i = 0; i < n; ++i)
        a[i] = in.nextInt();
      long[][] table = new long[(int) n][(int) n];
      for (long[] i : table)
        Arrays.fill(i, Long.MAX_VALUE / 2);
      for (int i = 0; i < n; ++i) {
        table[i][0] = a[i];
        long best = table[i][0];
        for (int j = 1; j < n; ++j) {
          long diff = (i - j + n) % n;
          table[i][j] = Math.min(table[i][j - 1], Math.min(table[i][j], a[(int) diff]));
        }
      }
      long ans = Long.MAX_VALUE / 2;
      for (int k = 0; k < n; ++k) {
        long test = k * x;
        for (int i = 0; i < n; ++i) {
          test += table[i][k];
        }
        ans = Math.min(ans, test);
      }
      out.println(ans);
    }    
    
  }
      
  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream));
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }
    
    public String nextLine() {
      try {
        return reader.readLine();
      } catch(IOException e) {
        throw new RuntimeException(e);
      }
    }

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

    public long nextLong() {
      return Long.parseLong(next());
    }
    
    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public boolean hasInput() {
      try {
        if (tokenizer != null && tokenizer.hasMoreTokens()) {
          return true;
        }
        reader.mark(1);
        int ch = reader.read();
        if (ch != -1) {
          reader.reset();
          return true;
        }
        return false;
      } catch(IOException e) {
        throw new RuntimeException(e);
      }
    }
    
  }
}


Measured memory_bytes: 40508
n,m=gets.split(" ").map{|k|k.to_i}
broken_step = []
pattern = [1,1,2]
broken_step[0] = -1
broken_step[m+1] = n+1
step = []
for i in 1..m
  broken_step[i] = gets.to_i
end
for i in 1..m+1
  step [i-1] = broken_step[i] - broken_step[i-1] - 2
end
if step.include?(-1) then
  puts 0
else
for i in 3..step.sort[-1] 
  pattern[i] = pattern[i-1] + pattern[i-2]
end
ans = 1
for i in 0..step.size-1
  ans = ans * pattern[step[i]]
end
puts ans%1000000007
end

Measured memory_bytes: 433020
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math
from bisect import bisect,bisect_right,bisect_left

def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))

a = get_int()
print(a+a**2+a**3)

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

ll sum[402][402], cst[402][402], n, v[402];

ll recur(int l, int r) {
    if(l == r) {
        cst[l][r] = 0;
        sum[l][r] = v[l];
        return 0;
    }
            
    if(cst[l][r] != -1)
        return cst[l][r];

    cst[l][r] = 10000000000000;
    for(int i = l; i < r; ++i) {
        recur(l, i), recur(i+1, r);
        if(cst[l][r] > cst[l][i]+cst[i+1][r]+sum[l][i]+sum[i+1][r])
            cst[l][r] = cst[l][i]+cst[i+1][r]+sum[l][i]+sum[i+1][r], sum[l][r] = sum[l][i] + sum[i+1][r];
    }

    return cst[l][r];
}

int main() {
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> v[i];

    memset(cst, -1, sizeof cst);
    cout << recur(0, n-1) << endl;
    return 0;
}

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

using namespace std;


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

	vector<vector<int>> h(n, vector<int>(3)), dp(n, vector<int>(3));

	for(auto &cur : h)
		cin >> cur[0] >> cur[1] >> cur[2];

	dp[0] = h[0];

	for(int i = 1; i < n; i++)
	{
		for(int j = 0; j < 3; j++)
		{
			for(int k = 0; k < 3; k++)
			{
				if(k == j)
					continue;

				dp[i][j] = max(dp[i][j], dp[i - 1][k] + h[i][j]);
			}
		}
	}

	cout << *max_element(dp[n - 1].begin(), dp[n - 1].end()) << endl;
}

Measured memory_bytes: 11136
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    string S;
    cin >> S;

    int def = 0;
    for (int i = 0; i < S.length(); i++) {
        if (S[i] == 'x') def++;
    }

    if (def < 8)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}


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

#include <vector>
using namespace std;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

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

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

typedef long long ll;

int n, m, q;
vector<int> a, b, c, d;
int ans;

void dfs(vector<int> A) {
    if (A.size() == n + 1) {
        int now = 0;
        rep(i, q) {
            if (A[b[i]] - A[a[i]] == c[i]) now += d[i];
        }
        ans = max(ans, now);
        return;
    }

    A.push_back(A.back());
    while (A.back() <= m) {
        dfs(A);
        A.back()++;
    }
}

int main() {
    cin >> n >> m >> q;
    a = b = c = d = vector<int>(q);
    rep(i, q) { cin >> a[i] >> b[i] >> c[i] >> d[i]; }
    dfs(vector<int>(1, 1));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T&v)
{fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0; return gcd(a, b, x, y);}
ll modpow(lll a,lll n,ll m){if(a==0)return a;lll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
const int N = 0;
int n, k;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> k;
  cout << (n%k ? 1 : 0) << endl;
  return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k; cin>>k;
    int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout<<a[k-1]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) // rep(i, 1, 5) --> {1,2,3,4} // rep(i, 5, 1) --> {4,3,2,1} // rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    string s;
    cin >> s;
    rep(i, 0, s.size())
        if (s[i] == ',')
            cout << " ";
        else 
            cout << s[i];
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[]  args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		
		for (int i = 0; i < n; i++) {
			String X = scanner.next();
			String Y = scanner.next();
			
			int[][] LCS_length = new int[X.length() + 1][Y.length() + 1];
			
			for (int j = 0; j <= X.length(); j ++) {
				LCS_length[j][0] = 0;
			}
			for (int k = 0; k <= Y.length(); k ++) {
				LCS_length[0][k] = 0;
			}
			
			for (int j = 1; j <= X.length(); j ++) {
				for (int k = 1; k <= Y.length(); k ++) {
					if (X.charAt(j - 1) == Y.charAt(k - 1)) {
						 LCS_length[j][k] = LCS_length[j - 1][k - 1] + 1;
					} else if (LCS_length[j - 1][k] > LCS_length[j][k - 1]) {
						LCS_length[j][k] = LCS_length[j - 1][k];
					} else {
						LCS_length[j][k] = LCS_length[j][k - 1];
					}
				}
			}
			
			System.out.println(LCS_length[X.length()][Y.length()]);
		}
		
		scanner.close();
	}
} 



Measured memory_bytes: 64576
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define Sort(a) sort(a.begin(),a.end())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z temp.cpp
//./a.out



int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
    int n;
    cin>>n;
    vi a(n),b(n),c(n);
    rep(i,n)cin>>a[i]>>b[i]>>c[i];
    vvi dp(n,vi (3,0));
    dp[0][0]=a[0];
    dp[0][1]=b[0];
    dp[0][2]=c[0];
    for(int i=1;i<n;i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
        dp[i][2]=max(dp[i-1][1],dp[i-1][0])+c[i];
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;

//////////////////////////////////////////////////////
return 0;}


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

#define ll  long long
#define pb push_back
#define mp make_pair
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
const int mod = 1000000007;


int main() {
    
    ll  n, wt;
    cin>>n>>wt;
    //v.resize(n+1);
    int w[n+1];
    int v[n+1];
    Fo(i,n){
        //int w,vo;
        cin>>w[i]>>v[i];
        
    }
    ll dp[n+1][wt+1];
    for(int i=0;i<=n;i++){

        for(int j=0;j<=wt;j++){
            if(i==0||j==0) dp[i][j]=0;
            else if(w[i]-j>0) dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);
        }
    }

    cout<<dp[n][wt];



    

    return 0;
}




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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e15;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 1e5 + 100;
const int LOG = 20;
const int mod = 1e9 + 7;
const int MX = 1e6 + 100;
typedef long long li;
const li MOD = 1000000000949747713ll;

ll dp[MAXN][4];
int a[MAXN][4];
void solve() {
    int n;
    cin >> n;

    for(int i=1;i<=n;++i){
        cin >> a[i][1] >> a[i][2] >> a[i][3];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=3;++j){
            for(int e=1;e<=3;++e){
                if(j!=e){
                    dp[i][j] = max(dp[i][j], dp[i-1][e] + a[i][j]);
                }
            }
        }
    }
    cout << max(dp[n][1], max(dp[n][2], dp[n][3]));

}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;

    while (t--)
        solve();
    dout <<endl<< (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

Measured memory_bytes: 4992
#include <iostream>
using namespace std;
int main(void) {
  int n, in, minv, maxv = -1000000000;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> in;
    if (i == 0) {
      minv = in;
      continue;
    }
    if (in - minv > maxv) maxv = in - minv;
    if (in < minv) minv = in;
  }
  cout << maxv << endl;
  return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const ll MOD = 1e9+7;

int main(){
  int n;
  cin >> n;
  vector<int> X(n);
  vector<int> A(n);
  rep(i, n) cin >> X[i];
  rep(i, n) A[i] = X[i];
  int n1 = n/2;
  int n2 = n1-1;
  sort(X.begin(), X.end());
  int g = X[n2];
  int h = X[n1];
  rep(i, n){
    if(A[i]<=g) cout << h << endl;
    else cout << g << endl;

  }
}

Measured memory_bytes: 3712
import heapq

N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)
for _ in range(M):
    tmp = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmp//2))
print(-sum(A))

Measured memory_bytes: 86444
/**
 *  author: MOOONI
 *  hackers are welcome!
**/
#include <bits/stdc++.h>

#define int long long

using namespace std;

template<typename T>
void debug_out(T x) {
  cerr << x;
}

template<typename A>
void debug_out(vector<A> v) {
  cerr << '{';
  for (int i = 0; i < (int) v.size(); i++) {
    if (i) {
      cerr << ", ";
    }
    debug_out(v[i]);
  }
  cerr << '}';
}

template <typename A, typename B>
void debug_out(pair<A, B> p) {
  cerr << '(';
  debug_out(p.first);
  cerr << ", ";
  debug_out(p.second);
  cerr << ')';
}

template <typename A, typename B, typename C>
void debug_out(tuple<A, B, C> p) {
  cerr << '(';
  debug_out(get<0>(p));
  cerr << ", ";
  debug_out(get<1>(p));
  cerr << ", ";
  debug_out(get<2>(p));
  cerr << ')';
}

template <typename A, typename B, typename C, typename D>
void debug_out(tuple<A, B, C, D> p) {
  cerr << '(';
  debug_out(get<0>(p));
  cerr << ", ";
  debug_out(get<1>(p));
  cerr << ", ";
  debug_out(get<2>(p));
  cerr << ", ";
  debug_out(get<3>(p));
  cerr << ')';
}

template <size_t N>
void debug_out(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  cerr << res;
}

template <typename T>
void debug_with_endl(T v) {
  debug_out(v);
  cerr << endl;
}

template <typename Head, typename... Tail> 
void debug_with_endl(Head H, Tail... T) {
  debug_with_endl(H);
  debug_with_endl(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:" << endl, debug_with_endl(__VA_ARGS__)
#else
#define debug(...) 2003
#endif

const int md = (int) 1e9 + 7;

int normalized(int x) {
  while (x < 0) {
    x += md;
  }
  x %= md;
  return x;
}

int sum() {
  return 0;
}

template <typename Head, typename... Tail> 
int sum(Head H, Tail...T) {
  return normalized(normalized(H) + sum(T...));
}

int mul() {
  return 1;
}

template <typename Head, typename... Tail> 
int mul(Head H, Tail...T) {
  return normalized(normalized(H) * mul(T...));
}

int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

int inv(int a) {
  return power(a, md - 2);
}

// pay attention to md's value first!
// use normalized form of modular integers for output!

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int k;
  cin >> k;
  auto Sum = [&](int x) {
    return mul(x, sum(x, 1), inv(2));
  };
  auto F = [&](int n, int k) {
    int x = Sum(k - 1);
    int y = (k == n + 1 ? Sum(n) : sum(Sum(n), mul(-1, Sum(n - k))));
    return sum(y, mul(-1, x), 1);
  };
  int ans = 0;
  for (int i = k; i <= n + 1; i++) {
    ans = sum(ans, F(n, i));
  }
  cout << normalized(ans) << '\n';
  return 0;
}

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

void solve(string s){
	int cnt = 0;
	for(int i = 0; i < s.size(); ++i) {
		if(s[i] == 'g') ++cnt;
		else --cnt;
	}
	cout << cnt / 2 << endl;
}

int main(){	
	string s;
	cin >> s;
	solve(s);
	return 0;
}



Measured memory_bytes: 512
require 'matrix'

#$stdin = DATA if $stdin.eof?

n, m, _ = gets.split.map(&:to_i)

a = n.times.map do
      gets.split.map(&:to_i)
    end

b = m.times.map do
      gets.split.map(&:to_i)
    end

ma = Matrix.rows(a)
mb = Matrix.rows(b)
mc = ma * mb

mc.row_vectors.each{|row| puts row.to_a.join("\s")}


Measured memory_bytes: 7632
from itertools import accumulate
def E(i, x):
    if i == 1:
        return 5 * x
    return (2 * i + 1) * x
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.sort(key=None, reverse=True)
x = list(accumulate(x))
x.insert(0, 0)
energy = 9223372036854775807
for k in range(1, N + 1):
    cost = (N + k) * X
    for i in range(1, N + 1):
        if i * k <= N:
            cost += E(i, x[i * k] - x[(i - 1) * k])
        else:
            cost += E(i, x[-1] - x[(i - 1) * k])
            break
    if cost < energy:
        energy = cost
print(energy)


Measured memory_bytes: 25252
N = int(input())
S = list(input())

count = 0
for i in range(1000):
    num = "{:03}".format(i)
    cursor = -1
    ok = True
    for c in num:
        slice = S[cursor + 1:]
        if c not in slice:
            ok = False
            break
        cursor += slice.index(c) + 1
    if ok:
        count += 1

print(count)

Measured memory_bytes: 4012
def main():
    monster_health, spells = map(int, input().split())
    attack = []
    damage = []
    for _ in range(spells):
        a, b = map(int, input().split())
        attack.append(a)
        damage.append(b)
    dp = [[float("inf") for _ in range(monster_health + 1)] for _ in range(spells + 1)]
    dp[0][0] = 0
    for i in range(1, spells + 1):
        for j in range(monster_health + 1):
            ind = min(j + attack[i - 1], monster_health)
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
            dp[i][ind] = min(dp[i][ind], dp[i][j] + damage[i - 1])
    print(dp[-1][-1])


if __name__ == '__main__':
    main()



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

template<class like_bool> inline void YES(like_bool condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class like_bool> inline void Yes(like_bool condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class like_bool> inline void POSS(like_bool condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class like_bool> inline void Poss(like_bool condition){ if(condition)cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class like_bool> inline void First(like_bool condition){ if(condition)cout << "First" << endl; else cout << "Second" << endl; }
int character_count(string text, char character){ int ans = 0; for(int i = 0; i < text.size(); i++){ ans += (text[i] == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
long gcd(long a, long b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }}
#define mod long(1e9 + 7)
#define bitcount(n) __builtin_popcount(n)

int main(){
    int N;
    cin >> N;
    for(int i = 0; true; i++){
        if(i * i > N){
            cout << (i - 1) * (i - 1) << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
//package BeginnerContest145;

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        FastReader sc = new FastReader();
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        if(n % 2 == 1){
            pw.println("No");
        }
        else{
            String s = sc.nextLine();
            if(s.substring(0,s.length()/2).equals(s.substring(s.length()/2))){
                pw.println("Yes");
            }
            else{
                pw.println("No");
            }
        }
        pw.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Measured memory_bytes: 21204
import java.util.*;
public class Main{
  public static void main(String[] args){
    //入力
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int q = sc.nextInt();
    String s = sc.next();
    int[] l = new int[q];
    int[] r = new int[q];
    for(int i=0; i<q; i++){
      l[i] = sc.nextInt();
      r[i] = sc.nextInt();
    }

    //右隣がCであるようなAを数える
    int[] at = new int[n];
    int t = 0;
    for(int i=1; i<n; ++i){
      if(s.charAt(i-1) == 'A' & s.charAt(i) == 'C')
        ++t;
      at[i] = t;
    }

    //lからrの間に'AC'があるかどうか調べる
    for(int i=0; i<q; ++i){
      //at[i個目のr] - at[i個目のl]
      System.out.println(at[r[i]-1] - at[l[i]-1]);
    }
  }
}


Measured memory_bytes: 102688
function Main(input) {
  var inputs = input.split("\n");
  var n_x = inputs[0].split(" ").map(e => parseInt(e, 10));
  var m = inputs.slice(1).filter(e => e).map(e => parseInt(e, 10));
  var sum = m.reduce((acc, cur) => acc + cur);
  var min = Math.min(...m);
  var cnt = m.length;
  var g = 0;
  var x = n_x[1] - sum;

  while(g <= x) {
    g += min;
    cnt += 1;
  }
  console.log(cnt - 1);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using namespace std;

typedef long long int ll;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl "\n"

vector <ll> v;

void generateAll(ll n, ll cur)
{
    if(n<15)
    {
        v.pb(cur);

        generateAll(n+1, cur*10+3);
        generateAll(n+1, cur*10+5);
        generateAll(n+1, cur*10+7);
    }
}

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

    ll N;
    cin >> N;

    generateAll(1, 3);
    generateAll(1, 5);
    generateAll(1, 7);

    ll ans = 0;

    for(ll i=0; i<sz(v); i++)
    {
        if(v[i] <= N)
        {
            ll c = v[i];

            ll flag[15];
            for(ll j=0; j<15; j++)
            {
                flag[j] = 0;
            }

            while(c)
            {
                flag[c%10]=1;
                c/=10;
            }

            if(flag[3] && flag[5] && flag[7])
            {
                ans++;
            }
        }
    }

    cout << ans << endl;    

    return 0;
}

Measured memory_bytes: 67936
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }


int main(int argc, char const *argv[])
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	string S;
	cin >> S;

	char c;
	bool result = true;
	for (size_t i = 0; i < S.size(); i++)
	{
		c = S[i];
		if (i % 2 == 0)
		{
			if (c == 'R' || c == 'U' || c == 'D')
			{
				
			} else {
				result = false;
			}
		} else {
			if (c == 'L' || c == 'U' || c == 'D')
			{
				
			} else {
				result = false;
			}
		}
	}
	
	if (result)
	{
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	

	return 0;
}


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

int main(){
    string s,t,c,u;
    cin >> s >> t;
    c=s;
    u=s;
    int v=t.length()-1;
    for(int i=s.length()-1;i>=0;i--){
        if(s[i]!=t[v]&&s[i]=='?'){
            s[i]=t[v];
            v--;
        }
        else if(s[i]!=t[v]&&s[i]!='?'){
            v=t.length()-1;
        }
        else if(s[i]==t[v]) v--;
        if(v<0) v=t.length()-1;
    }
    v=0;
    for(int i=0;i<u.length();i++){
        if(u[i]!=t[v]&&u[i]=='?'){
            u[i]=t[v];
            v++;
        }
        else if(u[i]!=t[v]&&u[i]!='?'){
            v=0;
        }
        else if(u[i]==t[v]) v++;
        if(v>=t.length()) v=0;
    }
    int a=0,b=0;
    int temp;
    if(s.rfind(t)!=string::npos||u.rfind(t)!=string::npos){
        if(u.rfind(t)!=string::npos) a=u.rfind(t);
        if(s.rfind(t)!=string::npos) b=s.rfind(t);
        if(s.rfind(t)!=string::npos||u.rfind(t)!=string::npos)
        temp=max(a,b);
        for(int i=0;i<s.length();i++){
            if(temp==i){
                cout << t;
                i+=t.length()-1;
            }
        else if(c[i]=='?') cout << "a";
        else cout << c[i];
        }
        cout << "\n";
    }
    else cout << "UNRESTORABLE" << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
arr = list(map(int, input().split()))

if N == 0:
    print(1 if arr[0]==1 else -1)
    exit()
elif arr[0] != 0:
    print(-1)
    exit()

# 末端の葉の数で初期化
sum_arr = [arr[-1]]*N
for i in range(1,N):
	# 深さi+1での頂点数 + 深さiでの葉の数
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
# 本来の順番に反転
sum_arr = sum_arr[::-1]

# 二分木の根から見ていく
ans = [1]*(N+1)
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    tmp = min((ans[i-1]-arr[i-1])*2,sum_arr[i-1])
    ans[i] = tmp

# for i in range(min(25,N+1)):
#     if ans[i] > 2**i:
#         print(-1)
#         exit()
if ans[N] != arr[-1]:
    print(-1)
    exit()

print(sum(ans))


Measured memory_bytes: 22236
<?php
// 入力
$s = trim(fgets(STDIN));

$n = strlen($s);

// 答え出力用配列に0格納
$result = array_fill(0, $n, 0);

// 計算
$cnt = 1;
$top = 0;
for ($i = 0; $i < $n; ++$i) {
    if ($i < $n - 1 && $s[$i] === $s[$i + 1]) {
        ++$cnt;
    } else {
        if ($s[$i] === 'R') {
            $target = $top + $cnt - 1;
            $result[$target] += ceil($cnt / 2);
            $result[$target + 1] += floor($cnt / 2);
        } else {
            $target = $top - 1;
            $result[$target] += floor($cnt / 2);
            $result[$target + 1] += ceil($cnt / 2);
        }
        $cnt = 1;
        $top = $i + 1;
    }
}

// 出力
echo implode(' ', $result).PHP_EOL;

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

int main() {
  int n, l;
  cin >> n >> l;
  string s[100];
  for(int i = 0; i < n; ++i) {
    cin >> s[i];
  }

  sort(s, s + n, less<string>());

  string joined;
  for(int i = 0; i < n; ++i) {
    joined += s[i];
  }

  cout << joined;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {-1, 0};
const int dx[] = {0, -1};
const int MAX_N = 80;
vector<vector<string>> memo(MAX_N, vector<string>(MAX_N));
int h, w;
bool IsNumber(char ch)
{
    if(ch >= 'A' && ch <= 'Z') return false;
    else return true;
};
string Cal(string s, string t)
{
    if(s.size() > t.size()) return s;
    else if(s.size() == t.size()) return max(s, t);
    else return t;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> w >> h, h | w)
    {
        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                char ch;
                cin >> ch;
                memo[i][j] = ch;
            }
        }
        string ans = "";
        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                if(!(IsNumber(memo[i][j][0]))) continue;
                string ms = "";
                for(int k = 0; k < 2; k++)
                {
                    int ny = i + dy[k];
                    int nx = j + dx[k];
                    if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
                    if(!(IsNumber(memo[ny][nx][0]))) continue;
                    if(memo[ny][nx][0] == '0' && memo[ny][nx].size() <= 1) continue;
                    ms = Cal(memo[ny][nx], ms);
                }
                memo[i][j] = ms + memo[i][j];
                ans = Cal(memo[i][j], ans);
            }
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3280
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef	long long ll;
typedef unsigned long long ull;
#define all(v) ((v).begin()),((v).end())
#define PI(n) ((double)acos(n))
#define clr0(n) (memset(n,0,sizeof n))
#define clr1(n) (memset(n,-1,sizeof n))
int dx8[8] = { 1, -1, 0, 0, 1, 1, -1, -1 };
int dy8[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	// online submission
#endif
}
void fast()
{
	std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
}
int a[120][120];
int main()
{
	
	int n, m;
	cin >> n >> m;
	cout << (n-1)*(m-1)  << endl;
}

Measured memory_bytes: 256
using System;

namespace UnityChan
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			int a, b;

			string[] str = Console.ReadLine ().Split(' ');
			a = int.Parse (str[0]);
			b = int.Parse (str[1]); 

			if(a > b)
				Console.WriteLine ("a > b");
			else if( a < b )
				Console.WriteLine ("a < b");
			else
				Console.WriteLine ("a == b");


		}
	}
}

Measured memory_bytes: 8848
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end())
#define vecmin(A) *min_element(A.begin(),A.end())
#define vecmax(A) *max_element(A.begin(),A.end())
typedef long long ll;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(){
  int n,k,L;
  cin >> n >> k >> L;
  UnionFind road(n+1);
  UnionFind train(n+1);
  rep(i,k){
    int p,q;
    cin >> p >> q;
    road.unite(p,q);
  }
  rep(i,L){
    int r,s;
    cin >> r >> s;
    train.unite(r,s);
  }
  map<pair<int,int>,int> mp;
  rep1(i,n)mp[make_pair(road.root(i),train.root(i))]++;
  rep1(i,n) cout << mp[make_pair(road.root(i),train.root(i))] << endl;
}

Measured memory_bytes: 13568
#include <iostream>
#include <cstdio>
#include <vector>
#define N 100005
using namespace std;

int n, c, ans[N];
bool v[N];
vector<int> gr[N], gi[N];

void f(int p, int q) {
	int i, j, ne;
	for (i = 0, j = 1; i < gr[p].size(); i++) {
		if (j == q) j++;
		ne = gr[p][i];
		if (v[ne]) continue;
		v[ne] = 1;
		ans[gi[p][i]] = j;
		f(ne, j);
		j++;
	}
}

int main()
{
	int i, t1, t2;
	cin >> n;
	for (i = 1; i < n; i++) {
		scanf("%d %d", &t1, &t2);
		gr[t1].push_back(t2); gi[t1].push_back(i);
		gr[t2].push_back(t1); gi[t2].push_back(i);
	}
	v[1] = 1;
	f(1, 0);
	for (i = 1; i < n; i++) c = max(c, ans[i]);
	cout << c << endl;
	for (i = 1; i < n; i++) printf("%d\n", ans[i]);
    return 0;
}

Measured memory_bytes: 13568
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll a,b,c,n;
cin>>a>>b>>c>>n;
ll ca=0;
for(ll i=0; i<=3000; i++){
for(ll k=0; k<=3000-i; k++){
if((n-i*a-k*b)>=0&&(n-i*a-k*b)%c==0){
ca++;}}}
cout << ca << endl;}


Measured memory_bytes: 3616
#include<cstdio>
#include<vector>
#include<climits>
using namespace std;

vector<vector<long long>> m;

int main(){
	vector<long long> a, cf; 
	int n,i,d,j,k;
	long long g;
	scanf("%d",&n);
	a = vector<long long>(n);	cf=vector<long long>(n);		
	m=vector<vector<long long>> (n,vector<long long>(n,(long long)1<<60));
	for(i=0; i<n; i++){	scanf("%lld",&a[i]);	m[i][i]=0;	}
	cf[0]=a[0];	for(i=1; i<n; i++)	cf[i]=cf[i-1]+a[i];
	for(d=1; d<n; d++){
		for(i=0; i<n-d; i++){
			j=i+d;
			for(k=i; k<j; k++){
				g=m[i][k]+m[k+1][j]+cf[j]-cf[i]+a[i];
				if(g<m[i][j])	m[i][j]=g;
			}
		}
	}
	printf("%lld\n",m[0][n-1]);
	for(i=0; i<n; i++)	m[i].clear();	a.clear();	cf.clear();
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

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

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

template<typename T>class BIT {
    public:
    int n;
    vector<T> bit;
    
    BIT(int n): n(n){
        bit.resize(n);
        fill(bit.begin(), bit.end(), (T)0);
    }

    void add(int idx, T x){
        for(int i=idx;i<=this->n;i+=i&-i) bit[i] += x;
    }

    //bit[1]からbit[end]までの和 (閉区間)
    T sum(int end){
        T ret = (T)0;
        for(int i=end;i>=1;i-=i&-i) ret += bit[i];
        return ret;
    }

    T count_swap(vector<int> v){
        T ret = (T)0;
        for(int i=1;i<=n;++i){
            add(v[i], 1);
            ret += i - sum(v[i]);
        }
        return ret;
    }
};


int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<BIT<int>> trees(26, BIT<int>(n+10));
    for(int i=0;i<n;++i) {
        trees[s[i]-'a'].add(i+1, 1);
    }
    int q, query;
    cin >> q;
    for(int i=0;i<q;++i) {
        cin >> query;
        if(query == 1) {
            int qi; char qc;
            cin >> qi >> qc;
            trees[s[qi-1]-'a'].add(qi, -1);
            s[qi-1] = qc;
            trees[qc-'a'].add(qi, 1);
        } else {
            int ql, qr, ans = 0;
            cin >> ql >> qr;
            for(int j=0;j<26;++j) {
                if(trees[j].sum(qr) - trees[j].sum(ql-1) > 0) {
                    ++ans;
                }
            }
            cout << ans << endl;
        }
    }
}


Measured memory_bytes: 53660
N=int(input())
A=[int(input()) for i in range(N)]
LM=[0,A[0]]
a=A[::-1]
RM=[a[0]]
for i in range(1,N-1):
    LM.append(max(LM[-1],A[i]))
    RM.append(max(RM[-1],a[i]))
RM=RM[::-1]+[0]
for i in range(N):
    print(max(LM[i],RM[i]))

Measured memory_bytes: 18872
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>
#include <string>
#include <regex>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
    int n, k;
    int v[50];
    int s[51] = {};
    int ans = -100000000;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        s[i+1] = s[i] + v[i];
    }
    for (int p = 0; p <= k && p <= n; p++) {
        for (int l = 0; l <= p; l++) {
            vector<int> t;
            int r = n - p + l;
            int a = s[n] - s[r] + s[l];
            for (int i = 0; i < l; i++) {
                t.push_back(v[i]);
            }
            for (int i = n-1; i >= r; i--) {
                t.push_back(v[i]);
            }
            sort(t.begin(), t.end());
            for (int i = 0; i < k - p && i < p; i++) {
                if (t[i] < 0) a -= t[i];
            }
            ans = max(ans, a);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#B
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
# print(a, b)
count=0
for i in a:
    for j in range(len(i)):
        i[j] *= b[j]
    if sum(i) > -c:
        count += 1

print(count)

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>

int main(void){
    int n,t, i, j, k;
    scanf("%d %d",&n,&t);
    for(i=0;i<=n;i++){
        for(j=0;j<=n-i;j++){
            k=n-i-j;
            if(1000*i+5000*j+10000*k==t){
                printf("%d %d %d\n",k,j,i);
                return 0;
            }
        }
    }
    puts("-1 -1 -1");
    return 0;
}

Measured memory_bytes: 128
import java.util.*;

import static java.lang.System.*;

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

        int[] x = new int[N];
        int[] y = new int[N];
        int[] h = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            h[i] = sc.nextInt();
        }

        for (int cx = 0; cx <= 100; cx++) {
            for (int cy = 0; cy <= 100; cy++) {
                int H = 0;
                for (int i = 0; i < N; i++) {
                    if (h[i] != 0) {
                        H = h[i] + Math.abs(x[i] - cx) + Math.abs(y[i] - cy);
                        break;
                    }
                }

                boolean isAns = true;
                for (int i = 0; i < N; i++) {
                    int htmp = Math.max(H - Math.abs(x[i] - cx) - Math.abs(y[i] - cy), 0);
                    if (htmp != h[i]) {
                        isAns = false;
                        break;
                    }
                }

                if (isAns) {
                    out.println(cx + " " + cy + " " + H);
                    return;
                }
            }
        }
    }
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  int n;
  cin >> n;
  cout << (n+1)/2 << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
import math
import itertools

n,T=list(map(int,input().split()))
num=[]
for i in range(n):
	c,t=list(map(int,input().split()))
	if T>=t:
		num.append(c)
if num==[]:
	print("TLE")
else:
	print(min(num)) 


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

int main(){
	int N;
	cin >> N;
	ll odd = 1;
	ll ans = 1;
	rep(i,N) {
		int a;
		cin >> a;
		if (a%2 == 0) odd *= 2;
		ans *= 3;
	}
	ans -= odd;
	cout << ans << endl;

	return 0;
}


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

int main () {
  int A, B;
  cin >> A >> B;
  if (A != 1 && B!= 1) {
    if (A > B) cout << "Alice" << endl;
    else if (A < B) cout << "Bob" << endl;
    else cout << "Draw" << endl;
  }
  else if (A == 1 && B == 1) cout << "Draw" << endl;
  else if (A == 1) cout << "Alice" << endl;
  else  cout << "Bob" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
#include <algorithm>
#include <functional>
#include<iostream>
#include <string>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define fro(i,j,n) for(int i=j;i<n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)


int main() {
    int n;
    string s;
    int ans=0;
	cin >> n>>s;
    int hajime=0;
    for(int i = 1;i<=n/2;i++){
      bool end = true;
      bool tugi = false;
      for(int j = hajime;j<=n-2*i;j++){
        for(int k=j+i;k<=n-i;k++){
          if(s.substr(j, i)==s.substr(k, i)){
            if(hajime<j)hajime=j;
            ans = i;
            tugi = true;
            end = false;
            break;
          }
        }
      if(tugi)break;
      }
    if(end)break;
    }
    cout<<ans<<endl;
}


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

int main()
{
    long long n, a[5];
    cin >> n;
    for(int i = 0; i < 5; ++i) cin >> a[i];
    sort(a, a + 5);
    long long ans;
    ans = n / a[0];
    if(n % a[0] == 0) ans = n / a[0] - 1;
    ans += 5;
    cout << ans << endl;

}


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

const int max_n = 1000000;
int prime[max_n];

int main(void){
    rep(i, max_n) prime[i] = 1;
    prime[0] = 0;
    prime[1] = 0;
    for(int i=2; i<=sqrt(max_n)+1; ++i) {
        if(prime[i] == 1) {
            for(int j=2; i*j<=max_n; ++j) {
                prime[i*j] = 0;
            }
        }
    }
    int n;
    while(cin >> n && n) {
        int ans = 0;
        for(int i=n+1; i<=2*n; ++i) {
            ans += prime[i];
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 5064