akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

int main(){
    using namespace std;
    unsigned long N;
    cin >> N;
    vector dp(N + 4, vector(3, 0L));
    vector<long> a(4);
    copy_n(istream_iterator<long>(cin), N, back_inserter(a));
    for(unsigned long i{4}; i < N + 4; ++i)if(i & 1)dp[i][1] = max({dp[i - 2][1] + a[i], dp[i - 3][0] + a[i], dp[i - 1][0]});
        else{
            dp[i][0] = dp[i - 2][0] + a[i];
            if(i > 4)dp[i][2] = max({dp[i - 2][2] + a[i], dp[i - 3][1] + a[i], dp[i - 4][0] + a[i], dp[i - 1][1], dp[i - 2][0]});
        }
    cout << dp.back()[1 + (N & 1)] << endl;
    return 0;
}

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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

string S;

signed main()
{
  int N, K;
  long double ans = 0;
  cin >> N >> K;

  vector<int> KK;

  // for(int n = N; 1 <= n; n--) {
  FOR(n,1,N+1) {
    long double tmp = (long double)1/N;
    int s = n;
    int cnt = 0;
    while(s < K) {
      cnt++;
      tmp *= (long double)0.5;
      s *= 2;
    }
    // ans += tmp;
    KK.push_back(cnt);
  }

  sort(begin(KK), end(KK));

  int pre = -1;
  int preK = -1;
  REP(i,KK.size()) {
    int k = KK[i];
    if(pre == -1) {
      pre = 1;
      preK = k;
    } else if(k == preK){
      pre++;
    } else {
      cerr << preK << " " << pre << endl;
      ans += (long double)pow(0.5, preK) * pre;
      // cerr << pre << " " << endl;
      pre = 1;
      preK = k;
    }
  }

  ans += (long double)pow(0.5, preK) * pre;

  printf("%.11Lf\n", ans / N);

  return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <string>
using namespace std;
string Ns;
int dfs(string n) {
  if(n.size() > 9 || n.size() > 0  && stoi(n) > stoi(Ns)) return 0;
  int used[10] = {0};
  for(int i = 0; i < n.size(); ++i) ++used[n.at(i)-'0'];
  int cnt = (used[3] > 0 && used[5] > 0 && used[7] > 0);
  cnt += dfs(n+"3")+dfs(n+"5")+dfs(n+"7");
  return cnt;
}
int main() {
  cin >> Ns;
  cout << dfs("") << endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
string s;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>s;
	ll x=0,ans=0;
	REP(i,(ll)s.size()-2){
		if(s.substr(i,3)=="ABC"){
			ans+=x+1;
			s[i+1]=(x==0?'C':'A');
			s[i+2]='A';
			x=max(x-1,0ll);
		}else if(s[i]=='A'){
			x++;
		}else{
			x=0;
		}
	}
	cout<<ans<<endl;
}

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

int main(){
	int N, D, i, j, k;
	cin >> N >> D;
	
	double X[N][D];
	for(i=0; i<N; i++){
		for(j=0; j<D; j++){
			cin >> X[i][j];
		}
	}
	
	int ans=0;
	for(i=0; i<N-1; i++){
		for(j=i+1; j<N; j++){
			double d = 0;
			for(k=0; k<D; k++){
				d += pow(X[i][k]-X[j][k],2);
			}
			d = sqrt(d);
			int tmp = d;
			if(d==tmp)	ans++;
		}
	}
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import sys

n=int(input())

left=0
right=n-1

print(left)
sl=input()
if sl=="Vacant":
  sys.exit()
print(right)
sr=input()
if sr=="Vacant":
  sys.exit()


sm=""
while right-left>=2:
  mid=(left+right)//2
  print(mid)
  sm=input()
  if sm=="Vacant":
    sys.exit()
  if (sl==sm and (mid-left)%2==0) or (sl!=sm and (mid-left)%2==1):
    left=mid
    sl=sm
  else:
    right=mid
    sr=sm

print(left)
if input()=="Vacant":
  sys.exit()
print(right)
if input()=="Vacant":
  sys.exit()
  
    


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

#define ll long long

int main()
{
 ll n,d,count=0;
 cin>>n>>d;

 while(n--)
 {
   ll x,y;
   cin>>x>>y;

   if(x<0) x = -1*x;
   if(y<0) y = -1*y;

   //cout<<endl<<x<<" "<<y;

   ll temp = x*x + y*y;

   //cout<<endl;

   //cout<<temp<<" "<<sqrt(temp)<<endl;

   if(sqrt(temp) <= d)
    count++;
 }
 cout<<count;
}


Measured memory_bytes: 3668
import Foundation

let arr=readLine()!.split{$0==" "}.map{Int(String($0))!}
var n=arr[0]
var k=arr[1]
var count:[Int] = []
var count2:[Int] = []

for i in 1...n {
    count.append(i)
}
for _ in 0..<k {
    let d = Int(readLine()!)!
    let j=readLine()!.split{$0==" "}.map{Int(String($0))!}
    for i in 0..<d {
        count2.append(j[i])
    }
}
let result = count2.reduce([], { $0.contains($1) ? $0 : $0 + [$1] })
print(count.count - result.count)

Measured memory_bytes: 13368
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        s: String
    };
    let mut n = 0;
    for c in s.chars() {
        if c == '1' {
            n += 1
        }
    }
    println!("{}", n);
}


Measured memory_bytes: 4352
#include <iostream>
    #include <string>
    #include <set>  
    #include <algorithm>
    #include <vector>
    #include <cmath>
    #include <queue>
    #include <deque>
    #include <cstring>
    #include <cstdio>
    #include <map>
    #include <numeric>
    #include <cassert>
    #include <iomanip>
    #include <sstream>
using namespace std;
const int MAXN=2e5+10;
int n;
long long a[MAXN],sum[MAXN];
int main()
{
	cin>>n;
	cin>>a[0];
	sum[0]=a[0];
	for(int i=1;i<n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	long long mn=1e18+7;
	for(int i=0;i<n-1;i++)
		mn=min(mn,abs(sum[i]-sum[n-1]+sum[i]));
	cout<<mn<<endl;
	return 0;
}

Measured memory_bytes: 3328
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<cmath>
#include<ctime>
#include<complex>

using namespace std;

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

long long p(int x){
	if(x==1) return 10;
	else return 10*p(x-1);
}

int f(long long y){
	if(y==2)  return 1;
	else{
		for(long long i=3;i*i<=y;i+=2){
			if(y%i==0){ return 0; break;}
		}
		return 1;
	}
}

int main(){

	int n,c;
	cin >> n >> c;

	if(c<0){
		if(n==1) cout << 11 << endl;
		else cout << p(n)-1 << p(n)-1 << endl;
	}

	else{

		for(long long i=p(2*n+1)-1;i>=p(2*n)+1;i-=2){
			bool b=false; long long r=i;
			for(int j=0;j<n;j++){
				if(r/p(2*(n-j))==r%10){
				   b=true;
				   r=(r%p(2*(n-j))-r%10)/10;
				}
				else{
				   b=false; break;
				}
			}

			if(b && r==c){
				if(f(i)){
					cout << i << endl; break;
				}
			}
		}
	}

	return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int h,w;
string c[maxn],s[maxn];
int visw[maxn],vish[maxn];
void dfsw(int x,int op)
{
	if(x==w)
	{
		cout<<"YES"<<endl;
		exit(0);
	}
	else if(visw[x]!=-1)
		dfsw(x+1,op);
	else
	{
		for(int i=x+1;i<=w-1;i++)
		{
			if(visw[i]!=-1)
				continue;
			int flag=0;
			for(int j=0;j<=h-1;j++)
			{
				if(s[vish[j]][i]!=s[j][x])
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
			{
				visw[x]=i;
				visw[i]=x;
				dfsw(x+1,op);
				visw[x]=-1;
				visw[i]=-1;
			}
		}
		if(op==1)
		{
			int flag=0;
			for(int j=0;j<=h-1;j++)
			{
				if(s[vish[j]][x]!=s[j][x])
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
			{
				visw[x]=x;
				dfsw(x+1,0);
				visw[x]=-1;
			}
		}
	}
}
void dfsh(int x,int op)
{
	if(x==h)
	{
		int opp=w%2;
		dfsw(0,opp);
	}
	else if(vish[x]!=-1)
		dfsh(x+1,op);
	else
	{
		for(int i=x+1;i<=h-1;i++)
		{
			if(vish[i]!=-1)
				continue;
			if(c[i]!=c[x])
				continue;
			vish[x]=i;
			vish[i]=x;
			dfsh(x+1,op);
			vish[x]=-1;
			vish[i]=-1;
		}
		if(op==1)
		{
			vish[x]=x;
			dfsh(x+1,0);
			vish[x]=-1;
		}
	}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>h>>w;
    for(int i=0;i<=h-1;i++)
	{
    	cin>>s[i];
    	c[i]=s[i];
    	sort(c[i].begin(),c[i].end());
    }
    memset(vish,-1,sizeof(vish));
    memset(visw,-1,sizeof(visw));
    int op=h%2;
    dfsh(0,op);
    cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 10664
(defun num-degit (n)
  (length (write-to-string n)))
(let ((n (read))
      (a (expt 2 64)))
  (loop for i from 1 to (truncate (sqrt n)) do
        (when (= (mod n i) 0)
          (setf a (min a (max i (truncate n i))))))
  (princ (num-degit a)))


Measured memory_bytes: 4704
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;

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

  vector<int> av;
  int a = 1;
  int ax = a*8/100;
  while(ax <= A) {
    if (ax == A) av.push_back(a);
    a++;
    ax = a*8/100;
  }
  vector<int> bv;
  int b = 1;
  int bx = b*10/100;
  while(bx <= B) {
    if (bx == B) bv.push_back(b);
    b++;
    bx = b*10/100;
  }
  int ans = INF;
  for (int a : av) {
    for (int b : bv) {
      if (a == b) {
        ans = min(ans, a);
      }
    }
  }
  if (ans == INF) ans = -1;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	private void doit() {
		while (true) {
			String a = sc.next();
			String b = sc.next();
			if(a.equals("0") && b.equals("0")) break;
			char [] c = (a + "").toCharArray();
			char [] d = (b + "").toCharArray();
			int hit = 0, blow = 0;
			boolean [] used = new boolean[c.length];
			for(int i = 0; i < c.length; i++){
				if(c[i] == d[i]){
					hit++;
					used[i] = true;
				}
			}
			
			for(int i = 0; i < c.length; i++){
				if(used[i]) continue;
				for(int j = 0; j < c.length; j++){
					if(i == j)continue;
					if(c[i] == d[j]){
						blow++;
						break;
					}
				}
			}
			System.out.println(hit + " " + blow);
		}
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

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

Measured memory_bytes: 46036
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack> 
#include<queue>
#include<cmath>
#include<map>
#define LL long long
#define N 400100
#define M 1010
#define MOD 1000000007
#define FOR(i,l,r) for (int i = (l); i <= (r); i ++)
#define CLR(a,x) memset(a,x,sizeof(a))
#define INF 0x3f3f3f3f
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define X first
#define Y second
using namespace std;
queue<int> q;
int vis[N], d[N];
int main(){
	int k;
	scanf("%d", &k);
	for (int i = 0; i < k; i ++) d[i] = INF;
	for (int i = 1; i <= 9; i ++){
		q.push(i % k);
		d[i % k] = min(d[i % k], i);
		vis[i % k] = 1;
	}
	while (!q.empty()){
		int u = q.front(); q.pop();
		vis[u] = 0;
		//printf("u = %d, d = %d\n", u, d[u]);
		for (int i = 0; i <= 9; i ++){
			int v = (u * 10 + i) % k;
			if (d[v] > d[u] + i){
				d[v] = d[u] + i;
				if (!vis[v]){
					vis[v] = 1;
					q.push(v);
				}
			}
			//printf("d[%d] = %d\n", v, d[v]);
		}
	}
	printf("%d\n", d[0]);
}

Measured memory_bytes: 1408
#! -*- coding:utf-8 -*-
O = str(input())
E = str(input())
O = list(O)
E = list(E)
n = 0
arr = []
for i in range(len(O)*2):
    if n % 2 == 0:
        try:
            arr.append(O.pop(0))
        except:
            pass
    else:
        try:
            arr.append(E.pop(0))
        except:
            pass        
    n += 1
try:
    arr.append(O.pop(0))
except:
    pass

for i in range(len(arr)-1):
    print(arr[i],end = '')

print(arr[-1])


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define str string
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a))
#define eps 1e-6
#define pi atan(1) * 4
#define mod 1000000007
#define inf 1000000000
#define llinf 1000000000000000000
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define FORl(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORDl(i, a, b) for (ll i = (a); i >= (b); i--)
using namespace std;
int main () {
  int h1, h2, m1, m2, k;
  scanf("%d %d %d %d %d", &h1, &m1, &h2, &m2, &k);
  printf("%d\n", h2 * 60 + m2 - h1 * 60 - m1 - k);
  return 0;
}

Measured memory_bytes: 3816
//3

#include <bits/stdc++.h>

using namespace std;

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

template<typename A, typename B> inline bool chmax(A &a, B b){if (a<b){a = b; return 1;}return 0;}
template<typename A, typename B> inline bool chmin(A &a, B b){if (a>b){a = b; return 1;}return 0;}

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<int,pii>pip;

const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
const bool debug = 0;

int M, N;
int w[212345], t[212345];
int c[212345], b[212345];
int sumw[212345], sumt[212345];
int dp[1<<15];

int main() {
	cin >> M >> N;
	REP(i, M) scanf("%d %d", w + i, t + i);
	REP(i, N) scanf("%d %d", c + i, b + i);
	
	REP(i, M) {
		sumw[i + 1] = sumw[i] + w[i];
		sumt[i + 1] = sumt[i] + t[i];
	}
	
	REP(i, 1<<N) {
		REP(j, N) if (!(i >> j & 1)) {
			int mc = upper_bound(sumw, sumw + M + 1, sumw[dp[i]] + c[j]) - sumw - 1;
			int tc = upper_bound(sumt, sumt + M + 1, sumt[dp[i]] + b[j]) - sumt - 1;
			chmax(dp[i | 1<<j], min(mc, tc));
		}
	}
	
	cout << dp[(1<<N)-1] << endl;
	
	return 0;
}

Measured memory_bytes: 6496
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;

int main() {
  int h, w;
  cin >> h >> w;
  vector<vi> cnt(h + 2, vi(w + 2, 0));
  vector<vc> a(h + 2, vc(w + 2, '.'));
  vi di = {-1, -1, -1, 0, 0, 1, 1, 1};
  vi dj = {-1, 0, 1, -1, 1, -1, 0, 1};
  rep2(i, 1, h + 1) rep2(j, 1, w + 1) {
    cin >> a[i][j];
    if(a[i][j] == '#')
      rep(k, 8) cnt[i + di[k]][j + dj[k]]++;
  }
  rep2(i, 1, h + 1) {
    rep2(j, 1, w + 1) {
      if(a[i][j] == '#')
        cout << '#';
      else
        cout << cnt[i][j];
    }
    cout << endl;
  }
}

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

typedef long long ll;

using namespace std;

//-------------------------↓↓↓↓↓↓------------------------

ll a[5001], le, ri, mid, n, k, ans;

bool okk(ll i){

  bool tmp, ok = true;

  if(k <= a[i]){
    return true;
  }

  bitset<5000 + 10> dp;
  dp[0] = true;

  for(int j = 0; j < n; j++){
    if(i == j)continue;
    dp |= (dp << a[j]);
  }

  for(int j = k - a[i]; j < k; j++){
    if(dp[j]){
      ok = false;
      break;
    }
  }

  if(!ok)tmp = true;
  else tmp = false;

  return tmp;

}

int main(void){

       cin.tie(0);
    ios::sync_with_stdio(false);

      cin >> n >> k;

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

      sort(a, a + n);

      le = 0, ri = n - 1, mid;

      while(ri - le > 1){

        mid = (le + ri) / 2;

        if(okk(mid)){
          ri = mid;
        }
        else{
          le = mid;
        }
        
      }

      if(!okk(ri))ans = ri + 1;
      else if(!okk(le))ans = le + 1;
      else ans = le;

      cout << ans << "\n";
    
       
return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	static int N, A[200000], ans = 0;
	cin >> N;
	for (int i = 0;i < N;++ i) cin >> A[i];
	sort(A, A+N);
	for (int i = 1 << 30;i > 0;i >>= 1) {
		for (int j = 0, k = N - 1;j < k;) {
			if (A[j] < 0 || A[k] > 0 && A[j] + A[k] < i) ++ j;
			else if (A[k] < 0 || A[j] + A[k] > i) -- k;
			else {
				A[j] = A[k] = -1;
				++ ans;
			}
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
def judge(n, k, a_list_s, f_list_s, v):
    res = 0
    # print(v)
    for i in range(n):
        a_necessary = v // f_list_s[i]
        # print(a_necessary, a_list_s[i])
        if a_list_s[i] > a_necessary:
            res += a_list_s[i] - a_necessary
    if res > k:
        return False
    else:
        return True


def solve_e(n, k, a_list, f_list):

    if sum(a_list) <= k:
        return 0
    
    a_list_s = sorted(a_list)
    f_list_s = sorted(f_list, reverse=True)

    left = 0
    right = 10 ** 12

    while right - left > 1:
        middle = (left + right) // 2
        if judge(n, k, a_list_s, f_list_s, middle):
            right = middle
        else:
            left = middle
    return right


def main():
    # input
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    f_list = list(map(int, input().split()))
    res = solve_e(n, k, a_list, f_list)
    print(res)


def test():
    assert solve_e(3, 5, [4, 2, 1], [2, 3, 1]) == 2
    assert solve_e(3, 8, [4, 2, 1], [2, 3, 1]) == 0
    assert solve_e(
        11, 14, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5],
        [8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2]) == 12


if __name__ == "__main__":
    test()
    main()


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

int main() {
  int H, W;
  cin >> H >> W;
  string a, b(W + 2, '#');
  for (cout << b << endl; H; H--) {
    cin >> a;
    cout << '#' << a << '#' << endl;
  }
  cout << b;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define cs const 
#define fr first 
#define se second
#define ls (now<<1)
#define mid ((l+r)>>1)
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define low(i) (i&(-i))
#define par pair<int,int>
#define cn(x) memset(x, 0, sizeof(x))
#define rep(i, x, y) for(int i=x; i<=y; ++i)
#define sep(i, x, y) for(int i=x; i>=y; --i)
#define fore(i, x) for(int i=fir[x]; i; i=nex[i])

cs int G = 3;
cs int N = 2e5;
cs int ff = 1e6 + 15;
cs int inf = 1e18 + 1;
cs int base = 2333;
cs int M = 998244353;
cs double eps = 1e-14;

int n, A[ff];
void init()
{
	cin >> n;
	rep(i, 1, n) scanf("%lld", &A[i]);
	sort(A + 1, A + 1 + n);
	int mn = 1;
	rep(i, 2, n - 1)
		if(min(A[mn], A[n] - A[mn]) < min(A[i], A[n] - A[i])) mn = i;
	cout << A[n] << " " << A[mn];
}
signed main()
{
	int Ts = 1;
	while(Ts--)
		init();
}

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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;

vector<pair<ll, ll> > prime_factorize(ll n){
    vector<pair<ll, ll> > res;
    for(int i = 2; i * i <= n; i++){
        if(n % i != 0) continue;
        ll ex = 0;
        while(n % i == 0){
            ex++;
            n /= i;
        }
        res.push_back({i, ex});
    }
    if(n != 1) res.push_back({n, 1});
    return res;
}

int main() {
    ll N; cin >> N;

    vector<ll> ex(N + 1, 0);
    for(ll i = 2; i <= N; i++){
        const auto &pf = prime_factorize(i);
        for(auto p : pf) ex[p.first] += p.second;
    }
    ll MOD = 1e9 + 7;
    ll ans = 1;
    for(int i = 2; i <= N; i++){
        ans *= ex[i] + 1;
        ans %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	// 整数の入力
	String s = sc.next();

	int ans = 0;
	for ( int i = 0; i <= 3; i++ ){
	    if (s.substring(i, i+1).equals("2")){
		ans++;
	    }
	}

	System.out.println(ans);
    }
}




Measured memory_bytes: 21844
using System;
using System.Collections.Generic;

namespace aoj
{
    class Program
    {
        class MyStack<T>
        {
            private static readonly int UnitLength = 100;

            public int Count = 0;

            private T[] stack;

            public MyStack()
            {
                this.stack = new T[100];
                this.Count = 0;
            }

            public T Pop()
            {
                if (this.Count <= 0) { return default(T); }

                var result = stack[this.Count - 1];

                stack[this.Count - 1] = default(T);
                --this.Count;

                //Console.WriteLine("pop: [" + this.Count + "] " + result);
                return result;
            }

            public bool Push(T _value)
            {
                if (this.Count == this.stack.Length)
                {
                    this.Increment();
                }

                ++this.Count;
                this.stack[Count - 1] = _value;

                //Console.WriteLine("push: [" + this.Count + "] " + _value);
                return true;
            }

            private void Increment()
            {
                T[] tmp = this.stack;
                this.stack = new T[this.stack.Length + UnitLength];
                Array.Copy(tmp, this.stack, tmp.Length);
            }
            
            private bool Decrement()
            {
                if (this.stack.Length - UnitLength < this.Count) { return false; }

                T[] tmp = this.stack;
                this.stack = new T[this.stack.Length - UnitLength];
                Array.Copy(tmp, this.stack, this.stack.Length);
                return true;
            }
        }

        static void Main(string[] args)
        {
            string[] array = Console.ReadLine().Split(' ');
            MyStack<string> stack = new MyStack<string>();
            for (var i = 0; i < array.Length; ++i)
            {
                if (array[i] == "+")
                {
                    var b = int.Parse(stack.Pop());
                    var a = int.Parse(stack.Pop());
                    stack.Push((a + b).ToString());
                    //Console.WriteLine("debug: + -> " + (a + b));
                }
                else if (array[i] == "-")
                {
                    var b = int.Parse(stack.Pop());
                    var a = int.Parse(stack.Pop());
                    stack.Push((a - b).ToString());
                    //Console.WriteLine("debug: - -> " + (a - b));
                }
                else if (array[i] == "*")
                {
                    var b = int.Parse(stack.Pop());
                    var a = int.Parse(stack.Pop());
                    stack.Push((a * b).ToString());
                    //Console.WriteLine("debug: * -> " + (a * b));
                }
                else
                {
                    stack.Push(array[i]);
                    //Console.WriteLine("debug: num -> " + array[i]);
                }
            }

            Console.WriteLine(stack.Pop());
        }
    }
}



Measured memory_bytes: 15972
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<double, double> Pdd;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;

const ll mod = 1e9+7;
const int INF = 2e9;
const double epsilon = 1e-7;
const double PI = 3.1415926535;

int a[100];
int c[100];
int main(void){
    int n; cin >> n; for(int i = 0;i < n;i++)cin >> a[i];
    sort(a, a+n);
    if(a[n-1] > n-1 || (a[n-1]+1)/2 > a[0]){printf("Impossible\n"); return 0;}
    fill(c, c+100, 0);
    for(int i = 0;i < n;i++)c[a[i]]++;
    if((a[n-1]%2 == 0 && c[a[0]] != 1) || (a[n-1]%2 == 1) && c[a[0]]!= 2){printf("Impossible\n"); return 0;}
    for(int i = a[0]+1;i <= a[n-1];i++){
        if(c[i]<2){printf("Impossible\n"); return 0;}
    }
    printf("Possible\n");
 	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main (){
	int a,b;
	scanf("%d%d",&a,&b);
	if(a>b)
	printf("a > b\n");
	else if(a<b)
	printf("a < b\n");
	else
	printf("a == b\n");
	return 0;
	}


Measured memory_bytes: 1976
def can_be_drawn(L):
        sum_len = 0
        max_len = 0
        for l in L:
                sum_len += l
                max_len = max(max_len, l)
        return 'Yes' if max_len < (sum_len - max_len) else 'No'


input()
L = [int(v) for v in input().split()]
print(can_be_drawn(L))

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define allR(v) v.rbegin(), v.rend()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
typedef pair<int,int> Pi;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m=numeric_limits<T>::max()){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int main() {
  ll A,V,B,W; cin >>A >>V >>B >>W;
  ll T; cin >>T;
  if (V <= W){
    cout <<"NO" <<endl; return 0;
  }
  if (T*(V-W) < abs(A-B)){
    cout <<"NO" <<endl;
  }else{
    cout <<"YES" <<endl;
  }
}

Measured memory_bytes: 3632
/*  ***  In The Name of God ... ***  */
#include <bits/stdc++.h>

using namespace std ;
 
typedef long long ll ;
typedef long double ld ;

 
#define int long long
#define all(v) v.begin() , v.end()

template<typename T> inline bool smin(T &a, const T &b){ return b < a ? a = b,1:0;}
template<typename T> inline bool smax(T &a, const T &b){ return a < b ? a = b,1:0;}

const int N = ( int ) 2e5 + 10 ;

int n , sum = 0 ; 
map < int , int > cnt ; 

int32_t main()                     
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n ;
	int res = 0 ;
	++ cnt [ 0 ] ; 
	while ( n -- ) {
		int x ;
		cin >> x ;
		sum += x ;
		res += cnt [ sum ] ;
		++ cnt [ sum ] ; 
	}
	cout << res << endl ; 
}


Measured memory_bytes: 12800
while True:
    m, f, r = map(int, input().split())
    if m == -1 and f == -1 and r == -1: break

    if m == -1 or f == -1: print('F')
    elif 80 <= m + f: print('A')
    elif 65 <= m + f < 80: print('B')
    elif 50 <= m + f < 65: print('C')
    elif 30 <= m + f < 50 and r >= 50: print('C')
    elif 30 <= m + f < 50: print('D')
    elif m + f < 30: print('F')


Measured memory_bytes: 5592
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()

int main() {
  //
  int n;
  cin >> n;
  vi x(n), y(n), h(n);
  rep(i, n) cin >> x[i] >> y[i] >> h[i];
  map<int, set<int>, greater<int> > m;
  rep(i, n) { m[h[i]].insert(i); }
  for (int cx = 0; cx <= 100; cx++) {
    for (int cy = 0; cy <= 100; cy++) {
      bool valid = true;
      int H = -1;
      for (auto& kv : m) {
        int hi = kv.first;
        for (auto& idx : kv.second) {
          int xi = x[idx];
          int yi = y[idx];
          // cout << hi << endl;
          if (hi > 0) {
            if (H < 0) {
              H = hi + abs(xi - cx) + abs(yi - cy);
            } else {
              // cout << hi << "," << H - abs(xi - cx) - abs(yi - cy) << endl;
              if (hi != H - abs(xi - cx) - abs(yi - cy)) {
                valid = false;
              }
            }
          } else {
            // cout << cx << "," << cy << ":" << H - abs(xi - cx) - abs(yi - cy)
            //      << ":" << valid << endl;
            if (H - abs(xi - cx) - abs(yi - cy) > 0) {
              valid = false;
            }
          }
        }
      }
      if (valid) {
        cout << cx << " " << cy << " " << H << endl;
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
TD=[list(map(int,input().split())) for i in range(N)]
TD.sort(key=lambda x:x[1],reverse=True)

ANS=0

check=[0]*(10**5+1)
NOCHANGE=[]
NETA=[]

for i in range(K):
    ANS+=TD[i][1]
    NETA.append(TD[i][0])


for i in range(N):
    if check[TD[i][0]]==0:
        NOCHANGE.append(i)
        check[TD[i][0]]=1

NOCHANSET=set(NOCHANGE)
NETA=len(set(NETA))



#NOWLIST=set(list(range(K)))
#NOWLIST=sorted(list(NOWLIST-NOCHANSET))



NOCHANGE=sorted(list(NOCHANSET))

ANS+=NETA**2

#print(NOCHANGE)
#print(NOWLIST)
#print(ANS)
#print(NETA)

L=len(NOCHANGE)

for j in range(L):
    if NOCHANGE[j]>K-1:
        break
else:
    j=L
#print(j)
i=K-1

SCORE=ANS
#print(SCORE)
while j<L:
    while i in NOCHANSET:
        i-=1

    if i<0:
        break


    SCORE+=TD[NOCHANGE[j]][1]-TD[i][1]-NETA**2+(NETA+1)**2
    if SCORE>ANS:
        ANS=SCORE
    #print(i,j,NETA,SCORE)
    NETA+=1
    j+=1
    i-=1

    #print(SCORE)


    #print(i,j)

print(ANS)

Measured memory_bytes: 39780
#pragma region Macros
#include <bits/stdc++.h>
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll;
#pragma endregion
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	string str;
	cin >> str;

	if (str[2] == str[3] && str[4] == str[5])
	{
		cout << "Yes" << '\n';
	}
	else
	{
		cout << "No" << '\n';
	}

	return 0;
}


Measured memory_bytes: 256
n,x = map(int,input().split())
a = sorted(list(map(int,input().split())))
now = x
for i in range(n):
    now -= a[i]
    if now < 0:
        print(i)
        exit()
    elif now == 0:
        print(i+1)
        exit()
print(n-1)

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

#define INF 100000001

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

    int v[N],w[N],sum_v(0);
    for(int i=0;i<N;i++){
        cin >> v[i] >> w[i];
        sum_v += v[i];
    }

    int dp[N+1][sum_v+1];   dp[0][0] = 0;
    for(int i=1;i<=sum_v;i++)   dp[0][i] = INF;

    for(int i=1;i<=N;i++){
        for(int j=0;j<=sum_v;j++){
            if(j<v[i-1]){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i-1]]+w[i-1]);
            }
        }
    }

    for(int i=sum_v;i>=0;i--){
        if(dp[N][i]<=W){
            cout << i << endl;
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 7044
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
#define MOD 1000000007LL

vector<vector<pair<int, P>>> num(90000, vector<pair<int, P>>(0));

ll func(int i, int j){
  if(j == 0) return 0;
  ll y1 = num.at(i).at(j-1).second.first;
  ll x1 = num.at(i).at(j-1).second.second;
  ll y2 = num.at(i).at(j).second.first;
  ll x2 = num.at(i).at(j).second.second;
  return abs(y2 - y1) + abs(x2 - x1);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll H, W, D;
  cin >> H >> W >> D;
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W ; j++){
      ll A;
      cin >> A;
      A--;
      num.at(A%D).push_back(make_pair(A, P(i, j)));
    }
  }
  for(int i = 0; i < D; i++){
    sort(ALL(num.at(i)));
  }
  vvll sum(D, vll(1, 0));
  for(int i = 0; i < D; i++){
    for(int j = 0; j < num.at(i).size(); j++){
      sum.at(i).push_back(sum.at(i).at(j) + func(i, j));
    }
  }
  ll Q;
  cin >> Q;
  vll ans(0);
  for(int i = 0; i < Q; i++){
    ll L, R;
    cin >> L >> R;
    L--; R--;
    ans.push_back(sum.at(L%D).at(R/D+1) - sum.at(L%D).at(L/D+1));
  }
  for(auto x: ans) cout << x << "\n";
}

Measured memory_bytes: 11256
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const int INF = 1e9 + 1;
using namespace std;
void solve(void)
{
    int h, w, n;
    cin >> h >> w >> n;
    int c_h = 0, c_w = 0;
    int x = 0;
    if (w > h)
        swap(h, w);
    while (x < n)
    {
        if (c_h < w)
            x += h - c_w, c_h++;
        else
            x += w - c_h, c_w++;
    }
    cout << c_h + c_w << endl;
}
int main(void)
{
    solve();
}

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

int main() {
  vector<pair<int, int>> v;
  for (int i = 0; i < 5; i++) {
    int n;
    cin >> n;
    int f, s = n;
    if (n % 10 == 0) f = 0;
    else f = 10 - n % 10;
    v.push_back(make_pair(f, s));
  }

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

  int ans = v[4].second;
  for (int i = 0; i < 4; i++) {
    ans += v[i].first + v[i].second;
  }

  cout << ans << endl;
}

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

int main(){
  string s; cin >> s;
  int n = s.size();
  vector<long long int> mods(2019, 0);
  long long int digit=1, mod=0;
  for(long long int i=n-1; i>=0; i--){
    mod = (mod + int(s[i] - '0') * digit) % 2019;
    digit = digit * 10 % 2019;
    mods[mod]++;
  }

  long long int ans = mods[0];
  for(int i=0; i<2019; i++){
    ans += mods[i] * (mods[i]-1) / 2;
  }

  cout << ans << endl;
}


Measured memory_bytes: 3756
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("filed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n:usize = read();
    let s:String = read();
    let mut chars:Vec<char> = s.chars().collect();
    let mut arr = vec![0;  n+1];
    arr[0] = chars[1..n].to_vec().iter().filter(|&&x| x == 'W').count();
    for i in 1..n {
        arr[i] = arr[i-1];
        if chars[i-1] == 'E' {
            arr[i] += 1;
        }
        if chars[i] == 'W' {
            arr[i] -= 1;
        }
    }
    println!("{}", n-arr.iter().max().unwrap()-1);
}


Measured memory_bytes: 5980
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, K = MAP()
    P = LIST()

    P.sort()

    print(sum(P[:K]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 10068
#include <bits/stdc++.h>
using namespace std;
int main() {
    #ifdef DEBUG
    std::ifstream in("/home/share/inputf.in");
    std::cin.rdbuf(in.rdbuf());
    #endif
    int N;
    int A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    A--, B--, C--, D--;
    string S;
    cin >> S;
    vector<bool> f(N + 2, false);
    f[B] = true;
    for(int i = B; i < D; i++) {
        if(f[i] && S[i] == '.') {
            f[i + 1] = f[i + 2] = true;
        }
    }
    bool across = D < C;
    vector<bool> s(N + 2, false);
    vector<bool> a(N + 2, false);
    s[A] = true;
    for(int i = A; i < C; i++) {
        if(s[i] && S[i] == '.') {
            s[i + 1] = s[i + 2] = true;
            if(f[i + 1] && S[i + 1] == '.' && i + 1 <= D) {
                a[i + 2] = true;
            }
        }
        if(a[i] && S[i] == '.') {
            a[i + 1] = a[i + 2] = true;
        }
    }
    if((!across && f[D] && s[C]) || (across && f[D] && a[C])) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 640
import sys
import copy
sys.setrecursionlimit(2147483647)

def main():
  H, W, K = map(int, input().split(' '))
  C = []
  for i in range(H):
    C.append(input())
  count = 0
  mani_row = []
  mani_col = []
  for i in range(2**H):
    for j in range(2**W):
      num = 0
      bini = format(i, f'0{H}b')
      binj = format(j, f'0{W}b')
      for h in range(H):
        for w in range(W):
          if(bini[h] == '0' and binj[w] == '0' and C[h][w] == '#'):
            num += 1
      if(num == K):
        count += 1
  print(count)






if __name__=='__main__':
  main()

Measured memory_bytes: 9344
N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**10
memory = [INF for _ in range(N)]
ans = 0
def search(x):
  l = 0
  r = len(memory) - 1
  cp = (l + r) // 2
  while r - l >= 0:
    cp = (l + r) // 2
    if memory[cp] >= x:
      r = cp - 1
    else:
      l = cp + 1
  return l
ans = 0 
for a in A:
  point = search(a)
  memory[point] = a
  ans = max(ans, point)

print(ans + 1)


Measured memory_bytes: 10344
n = int(raw_input())


matrix = []
for _ in xrange(2) :
    matrix.append(map(int, raw_input().strip().split(' ')))


for c in xrange(1, len(matrix[0])) : 
    matrix[0][c] += matrix[0][c - 1]

for r in xrange(1, len(matrix)) : 
    matrix[r][0] += matrix[r - 1][0]
    for c in xrange(1, len(matrix[r])) : 
        matrix[r][c] += max(matrix[r - 1][c], matrix[r][c - 1])

print matrix[-1][-1]


Measured memory_bytes: 2568
read = lambda: list(map(int, input().split()))
n = int(input())
a = read()

s = sum(a)
mod = 10 ** 9 + 7
ans = 0

for i in range(n - 1):
    s -= a[i]
    ans += a[i] * s
    ans %= mod
print(ans)

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

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

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

int main(){
    ll a, b;
    cin >> a >>b;
    ll ans = lcm(a,b);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long N; cin >> N;
	for(long long i = sqrt(N); i >= 1; i--){
		if(N % i == 0){
			cout << i + (N / i) - 2 << endl;
			break;
		}
	}
}

Measured memory_bytes: 256
import sys


def main():

    N = int(sys.stdin.readline().rstrip())

    A = [0] * (10**4 + 1)

    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                n = x**2 + y**2 + z**2 + x * y + y * z + z * x
                if n <= 10**4:
                    A[n] += 1

    for i in range(1, N + 1):
        print(A[i])

    return


main()


Measured memory_bytes: 9432
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define deb(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;

typedef long long int ll;
typedef string str;

int main ()
{
	// ios::sync_with_stdio(0);
 //    cin.tie(0);
 //    cout.tie(0);
	ll t,n,m,k,i,a,b,j;
	cin >> n >> k;
	ll arr[n+2];
	for(i=0;i<n;i++)
	{
		cin >>arr[i];
	}
	j=0;
	for(i=k;i<n;i++)
	{
		if(arr[j]<arr[i])
			cout << "Yes\n";
		else
			cout << "No\n";
		j++;
	}
	return 0;
}

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


signed main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int N,W;
	cin >> N >> W;
	int weight[N] , value[N];
	for(int i=0;i<N;i++) cin >> weight[i] >> value[i];
	
	// observe that total value lies in [100, 100000]
	// dp[i] --> min weight to have value exactly i

	int dp[100000+1];
	unordered_set<int> usedindices[100000+1];

	dp[0] = 0;
	for(int v=1;v<=100000;v++){
		dp[v] = -1; // denotes not possible
		int bestind = -1;
		int minweight = INT_MAX;

		for(int i=0;i<N;i++){
			if(value[i]>v) continue;

			int leftvalue = v-value[i];
			if(dp[leftvalue]==-1) continue;
			if(usedindices[leftvalue].count(i) >0 )continue;

			if( weight[i] + dp[leftvalue] < minweight){
				minweight = weight[i] + dp[leftvalue];
				bestind = i; 
			}
		}
		// if(v==7) cout << "v=7 bestind=" << bestind << endl;
		if(bestind==-1) continue;
		dp[v] = minweight;
		usedindices[v].insert(bestind);
		for(int x : usedindices[v-value[bestind]]) usedindices[v].insert(x);
	}
	
	// for(int i=0;i<=40; i++){
	// 	cout << "v=" << i << " w=" << dp[i] << endl;
	// }

	for(int i=100000;i>=0;i--){
		if(dp[i]!=-1 && dp[i]<=W) {
			cout << i << endl;
			break;
		}
	}

	return 0;
}

// v 0 1 2 3 4 5 6 7  8  9
// w 0 x 7 x 6 3 5 10 12 9

// w v
// 3 5
// 5 6
// 6 4
// 6 5
// 6 6
// 7 2


Measured memory_bytes: 106624
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

long long int gcd(long long int m, long long int n)
{
	if(n == 0) return m;
	return gcd(n, m % n);
}

long long int solve(long long int n, long long int c, long long int d)
{
	// 1 ~ nのうちcでもdでも割り切れないものの数
	// 全部の数は n
	// 割り切れるものの数は n / c
	return n - (n / c) - (n / d) + (n / (c * d / gcd(max(c, d), min(c, d))));
}

int main()
{
	long long int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << solve(b, c, d) - solve(a - 1, c, d) << endl;
}

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

typedef long long ll;
#define INF INT_MAX
#define MAXN 10005

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

ll maxself(ll a,ll b){
    if(a > b)return a;
    return b;
}

ll minself(ll a,ll b){
    if(a < b)return a;
    return b;
}

int N;


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

    cin >> N;
    vector<int> v(N);
    for(int i = 0 ; i < N ; i++)
        cin >> v[i];
    
    ll ans = INF;
    for(int p = 1 ; p <= 100 ; p++){
        ll temp = 0;
        for(auto x : v){
            temp += (x - p) * (x - p);
        }
        ans = minself(ans,temp);
    }
    cout << ans << '\n';

    return 0;
        
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	double a,b,x,w,h,ans;
	cin>>a>>b>>x;
	w=x*2/a/b;
	if(w<=a)ans=atan2(b,w)*(180/PI);
	else{
		h=x*2/a/a;
		ans=atan2(b-(h-b),a)*(180/PI);
	}
	fcout(8)<<ans<<endl;
	
	
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>

using namespace std;

int main(void){

    int n;
    int ku[9][9];
    bool flag = false;

    for(int i = 1;i <= 9;i++){
        for(int j = 1;j <= 9;j++){
            ku[i-1][j-1] = i*j;
        }
    }

    cin >> n;

    for(int i = 1;i <= 9;i++){
        for(int j = 1;j <= 9;j++){
            
            if(n == ku[i-1][j-1]){
                flag = true;
                break;
            }
            
        }
    }

    cout << (flag?"Yes":"No") << endl;

    return 0;
}

Measured memory_bytes: 256