akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A[] = new int[N];
		int B[] = new int[N];
		int C[] = new int[N-1];
		
		for(int i=0;i<N;i++) {
			A[i]=sc.nextInt();
		}
		for(int i=0;i<N;i++) {
			B[i]=sc.nextInt();
		}
		for(int i=0;i<N-1;i++) {
			C[i]=sc.nextInt();
		}
		
		int ans = 0;
		int before = -100;
		for(int i=0;i<N;i++) {
			ans += B[A[i]-1];
			if(before + 1 == A[i]) {
				ans+=C[A[i]-2];
			}
			before = A[i];
		}
		
		System.out.println(ans);
		
 	}
}


Measured memory_bytes: 23764
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	s = reverse(s)

	ss := map[string]bool{"maerd": true, "remaerd": true, "esare": true, "resare": true}

	t := ""
	for i := 0; i < len(s); i++ {
		t += string(s[i])
		if ss[t] {
			t = ""
		}
		if 7 < len(t) {
			break
		}
	}

	if t == "" {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}

}

func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}


Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int r; cin >> r;
  double pai = 3.1415926535;
  cout << fixed << setprecision(5) << 2*pai*r << endl;

  system("pause");
}


Measured memory_bytes: 3784
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std; 
int main(){
	int a[10],b[10];
	for(int i=0;i<10;i++)cin>>a[i];
	for(int i=0;i<10;i++)cin>>b[i];
	sort(a,a+10);sort(b,b+10);
	cout<<a[9]+a[8]+a[7]<<" "<<b[9]+b[8]+b[7]<<endl;


	return 0;
}

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , "; logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 4005*4005;

/* ...o(^-^)o... */


long long gcd(long long x, long long y){
    if (x > y)
        return gcd(y, x);
    long long m = 1;
    while(m != 0){
        m = y % x; y = x; x = m;
    }
    return y;
}

bool solve(lint a, lint b, lint c, lint d){
    if(a<b) return false;
    if(d<b) return false;
    if(b<=c) return true;
    lint g = gcd(b,d);
    if(a%g+b-g>c) return false;
    return true;
}

int main(){
    int t; cin >> t;
    rep(i,t){
        lint a,b,c,d; cin>>a>>b>>c>>d;
        bool res = solve(a,b,c,d);
        out(res?"Yes":"No");
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
 #define rep(i, n) for (int i = 0; i < (int)(n); i++)
 #define big 1000000007
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n){
        cin >>a[i];
    }
    int count=0;
    int same=1;
    int i=0;
    while(i<n){
        if(a[i]==a[i+1]){
            int j=1;
            while(a[i]==a[i+j]&&i+j<n){
                j++;
            }
            count += j/2;
            i += j;
        }
        else{
            i++;
        }
    }
    cout <<count<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ld long double
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
// const ll INF = 1LL << 30;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

void print(Vl vec){
    rep(i, 0, sz(vec)){
        if(i) cout << " ";
        cout << vec[i];
    }
    coel;
}

////////////////////////////////////////////////////////


int main() {
    ll n, m, k; cin >> n >> m >> k;
    Vl a(n+1), b(m+1);
    Rep(i, 1, n) cin >> a[i];
    Rep(i, 1, m) cin >> b[i];
    Rep(i, 1, n) a[i] += a[i-1];
    Rep(i, 1, m) b[i] += b[i-1];
    // print(a);
    // print(b);
    ll ans = 0;
    for(int i = n; i >= 0; i--){
        if(a[i] > k) continue;
        ll s = k - a[i];
        ll j;
        auto it = upper_bound(ALL(b), s);
        j = it-1 - b.begin();
        chmax(ans, i+j);
    }
    co(ans);

    return 0;
}



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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  int N = nextInt();
  vector<int> A(N), B(N);
  REP(i, N) A[i] = nextInt();
  REP(i, N) B[i] = nextInt();

  vector<int> v(N);
  REP(i, N) v[i] = i+1;
  int x = 0, y = 0;

  int rank = 0;
  do {
    if (v == A) x = rank;
    if (v == B) y = rank;
    rank++;
  } while (next_permutation(ALL(v)));
  cout << abs(x - y) << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.14159265358979323

//int calc1(float a,float b,float c,float d,float e,float f,float *x,float *y);
//void quick(int *,long long,long long);
//int comp(char *a,char *b);

int main(){
	
	int a[80],b[80],c[80];
	int m,n,i,j,wa,kuri,kazu;
	char buf[1000];

	scanf("%d",&kazu);
	for(j=0;j<kazu;j++){
		for(i=0;i<80;i++)
			a[i]=0;
		for(i=0;i<80;i++)
			b[i]=0;
		for(i=0;i<80;i++)
			c[i]=0;

		scanf("%s",buf);
		for(n=0;buf[n]!='\0';n++);
		if(n>80){
			scanf("%s",buf);
			printf("overflow\n");
			continue;
		}
		n--;
		for(i=0;i<=n;i++)
			a[i]=buf[n-i]-'0';

		scanf("%s",buf);
		for(m=0;buf[m]!='\0';m++);
		if(m>80){
			printf("overflow\n");
			continue;
		}
		m--;
		for(i=0;i<=m;i++)
			b[i]=buf[m-i]-'0';
		
		kuri=0;
		for(i=0;i<=n||i<=m;i++){
			wa=(kuri+a[i]+b[i])%10;
			kuri=(kuri+a[i]+b[i])/10;
			c[i]=wa;
		}
		if(kuri!=0){
			if(i>=80){
				printf("overflow\n");
				continue;
			}
			c[i]=kuri;
		}else
			i--;
		while(i>=0){
			printf("%d",c[i]);
			i--;
		}
		printf("\n");
	}
	//for(i=0;i<=1000000000;i++);
	return 0;
}

Measured memory_bytes: 612
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#define int long long
#define endre getchar();getchar();return 0
#define moder 1000000007
#define inf 1000000000000000000
#define rep(i,n) for(int i=0;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int kai(int x) {
	if (x == 0)return 1;
	return (kai(x - 1)*x) % moder;
}
int comb(int x, int y) {
	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;
}
map<int, int> factor(int m) {
	map<int, int>res;
	for (int i = 2; i*i <= m; i++) {
		while (m%i == 0) {
			res[i]++;
			m /= i;
		}
	}
	if (m != 1)res[m]++;
	return res;
}

/*--------Library Zone!--------*/

int n, z, w, a[2005];
signed main() {
	cin >> n >> z >> w;
	rep(i, n)cin >> a[i];
	if (n == 1) {
		cout << abs(a[0] - w) << endl;
	}
	else {
		cout << max(abs(a[n - 2] - a[n - 1]), abs(a[n - 1] - w)) << endl;
	}
	endre;
}

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

ll n, r, i;

inline ll read(){
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		if (ch == '-') w *= -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * w;
}

int main(){
	n = read(), r = read();
	while (n != 0){
		n /= r;
		i++;
	}
	printf("%lld\n", i);
	return 0;
}

Measured memory_bytes: 256
a=int(input())
b=input().split(' ')
m=0
s=1
i=0
o=0
while i<a:
    if int(b[i])==0:
        print(0)
        o=o+1
    i=i+1
while m<a and o==0:
    s=s*int(b[m])
    m=m+1
    if s>10**18 and o==0:
        print(-1)
        o=o+1
        break

if o==0:
    print(s)


Measured memory_bytes: 19408
#include<iostream>
#include<vector>
#include<iomanip>
#include<cmath>
using namespace std;

int main()
{
    char name[4];
    cin>>name;
    if(name[1]=='R')
    {
        cout<<"ABC";
    }
    else
    {
        cout<<"ARC";
    }
}


Measured memory_bytes: 3632
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int size = 100000 + 5;
int t[size], c, k, cnt, tot, n;
int main()
{
	scanf("%d%d%d", &n, &c, &k);
	for (int i = 0; i < n; i++)
		scanf("%d", &t[i]);
	sort(t, t + n);
	cnt = tot = 1;
	int cur = 0;
	for (int i = 1; i < n; i++) {
		if (cnt < c && t[i] - t[cur] <= k)
			cnt++;
		else {
			cnt = 1;
			tot++;
			cur = i;
		}
	}
	printf("%d", tot);
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int a,b;
	cin >> a >> b;
	if(a + b == 15) cout << "+" << endl;
	else if(a * b == 15) cout << "*" << endl;
	else cout << "x" << endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define inf 0x3f3f3f3f
#define pb push_back
#define vi vector<int>
#define fi first
#define se second 
#define mp make_pair
typedef unsigned long long ull;
//typedef pair<int,int> P;
#define LL long long 
#define pi acos(-1)
#define MOD 998244353
typedef long long ll;
using namespace std;
const int maxn = 100005; 
const char p[]="AGC";
struct item{
	ll a,b;
	bool operator<(const item&it)const{
		return a<it.a;
	}
}c[maxn];
int n,m;
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>c[i].a>>c[i].b;
	sort(c,c+n);
	ll tot=0,i=0,ans=0;
	while(tot<m){
		if(m-tot<=c[i].b){
			ans += (m-tot)*c[i].a;
			break;
		}
		ans += c[i].b*c[i].a;
		tot+=c[i].b;
		i++;
	}
	cout<<ans<<endl;
	return 0;
}


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	string s;
	cin>>s;
	int a=0,z=s.size()-1;
	while(s.at(a)!='A')++a;
	while(s.at(z)!='Z')--z;
	cout<<z-a+1<<"\n"s;
}

Measured memory_bytes: 720
n = int(input())
a = list(map(int, input().split()))

stand = [0] * n
for i in range(1, len(a)):
    if (a[i-1] + stand[i-1]) > a[i]:
        stand[i] = (a[i-1] + stand[i-1]) - a[i]

print(sum(stand))

Measured memory_bytes: 32228
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,s,n) for(int i=s;i<n;i++)
#define per(i,s,n) for(int i=n-1;i>=s;i--)
#define fi first
#define se second
#define all(c) c.begin(),c.end()
typedef long long int ll;
typedef pair<int, int> P;
typedef long double ld;
void Ans(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

const ll INF=1001001001;
const ll mod=1000000007;

int main(){
  int n;
  cin>>n;
  int a[n];
  rep(i,n) cin>>a[i];
  
  vector<P> p;
  int nowl=a[0];
  int nowh=0;
  int now=0;
  
  while(now<=n){
    while(a[now]<=nowl&&now<n){
      nowl=a[now];
      now++;
    }
    nowh=a[now];
    if(n==now) break;
    while(a[now]>=nowh&&now<n){
      nowh=a[now];
      now++;
    }
    p.push_back(P(nowl,nowh));
    nowl=a[now];
  }
  ll ans=1000;
  for(P x:p){
    //cout<<x.fi<<" "<<x.se<<endl;
    ans=(ans/x.fi)*x.se+ans%x.fi;
  }
  
  cout<<ans<<endl;
}


Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>

typedef long long ll;

ll gcd(ll a, ll b) {
    if(b > a) {
        std::swap(a, b);
    }

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

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

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

    ll gcdn = gcd(a[0], a[1]);
    for (int i = 2; i < n; i++)
    {
        gcdn = gcd(gcdn, a[i]);
    }

    std::cout << gcdn << std::endl;
}

Measured memory_bytes: 1024
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int main()
{
	int n,k;
	cin>>n>>k;
	if(n%k==0) cout<<0<<endl;else cout<<1<<endl;
}


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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

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

int N;

struct Edge {
  Edge(int _from, int _to, int _cost)
    : from(_from), to(_to), cost(_cost){}
  int from;
  int to;
  int cost;
};

vector< Edge > e;
// bool state[MAX_N];

struct UnionFind {
  vector< int > par;
  UnionFind(int n = 1) {
    init(n);
  }

  void init(int n) {
    par.resize(n);
    for(int i = 0; i < n; i++)
      par[i] = -1;
  }
  
  int root(int n) {
    if (par[n] < 0) return n;
    return par[n] = root(par[n]);
  }

  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (par[x] > par[y]) swap(x, y);
    par[x] += par[y];
    par[y] = x;

    return true;
  }
};

int kruscal()
{
  sort(ALL(e), [](Edge x, Edge y) {
      return x.cost < y.cost;
    });

  UnionFind uf(N);
  int res = 0;
  EACH(ei, e) {
    // if (state[ei.from] && state[ei.to]) continue;
    if (uf.root(ei.from) != uf.root(ei.to)){
      uf.unite(ei.from, ei.to);
      // state[ei.from] = state[ei.to] = true;
      res += ei.cost;
    }
  }

  return res;
}


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

  cin >> N;
  // x, y, i
  vector< tuple< int, int, int > > x(N);
  // y, x, i
  vector< tuple< int, int, int > > y(N);
  REP(i, N) {
    CIN(p, q);
    x[i] = make_tuple(p, q, i);
    y[i] = make_tuple(q, p, i);
  }
  
  sort(ALL(x));
  sort(ALL(y));

  REP(i, N - 1) {
    // x
    int tmp1, tmp2, from, to, cost;
    tie(tmp1, tmp2, from) = x[i];
    tie(tmp2, cost, to) = x[i + 1];
    e.emplace_back(Edge(from, to, abs(tmp2 - tmp1)));
  }
  
  REP(i, N) {
    // y
    int tmp1, tmp2, from, to, cost;
    tie(tmp1, tmp2, from) = y[i];
    tie(tmp2, cost, to) = y[i + 1];
    e.emplace_back(Edge(from, to, abs(tmp2 - tmp1)));    
  }

  int ans = kruscal();
  cout << ans << endl;
  
  return 0;
}



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



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

	for (int i = 1; i <= 360; i++) {
		if ((i*X) % 360 == 0) {
			cout << i;
			return 0;
		}
	}
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int n;
int arr[2005];
int cache[2006][2006];
vector<pair<int,int>>v;
int dp(int st,int en)
{
    int pos=st+n-1-en;
    if(pos==n)
        return 0;
    int &ans=cache[st][en];
    if(ans!=-1)
        return ans;
    ans=max(v[pos].first * abs(st-v[pos].second) + dp(st+1,en),
        v[pos].first * abs(en-v[pos].second) + dp(st,en-1));
    return ans;
}
int32_t main() 
{
    IOS;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        v.push_back({arr[i],i});
    }
    sort(v.rbegin(),v.rend());
    memset(cache,-1,sizeof(cache));
    cout<<dp(0,n-1);
}   


Measured memory_bytes: 35272
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
	static final int MAX = 2_147_483_646; // intMax 
	static final int INF = 1_000_000_000; // 10^9  
	public static void main(String[] args) throws Exception{
		hayami saori = new hayami();
		int n = saori.saori_hayami();
		long sum = 0;
		long[] count = new long[100001];
		for(int i = 0;i < n;i++){
			int num = saori.saori_hayami();
			count[num]++;
			sum += num;
		}
		int q = saori.saori_hayami();
		for(int i = 0;i < q;i++){
			int b = saori.saori_hayami();
			int c = saori.saori_hayami();
			sum += (c - b)*count[b];
			count[c] += count[b];
			count[b] = 0;
			System.out.println(sum);
		}
		saori.close();
	}
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}


Measured memory_bytes: 54184
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>	
#include <deque>
#include <set>
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define fore(i,a) for(auto &i:a)
#define INF INT_MAX/2;
const int INF2 = 1001001001;
typedef long long ll;
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
using namespace std;
using Graph = vector<vector<int>>;


int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}


 // 最大公約数計算
 
ll gcd(ll a, ll b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
// 最小公倍数の計算

ll lcm(ll a, ll b)
{
	ll g = gcd(a, b);

	return a / g * b;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


	void init(int n)
	{
		for (int i = 0; i < n; i++) par[i] = i;
		for (int i = 0; i < n; i++) r[i] = 0;
	}

	int find(int x)
	{
		if (par[x] == x)return x;
		else return find(par[x]);
	}

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (r[x] < r[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if (r[x] == r[y])
			{
				r[x]++;
			}
		}
	}
};

const int MAX_N = 110000;

int memo[MAX_N];

int rec(int n) {
	if (n == 0)return 0;
	if (memo[n] != -1)return memo[n];

	int res = n;

	for (int pow6 = 1; pow6 <= n; pow6 *= 6)res = min(res, rec(n - pow6) + 1);

	for (int pow9 = 1; pow9 <= n; pow9 *= 9)res = min(res, rec(n - pow9) + 1);

	return memo[n] = res;
}

int calc(int x) {
	int ret = 0;
	while (x % 2 == 0) {
		x /= 2;
		ret++;
	}

	return ret;
}

int a[12][12];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;

	cin >> n;

	if (0<=n &&n<=9){
		if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9) {
			cout << "hon" << endl;
			return 0;
		}
		else if (n == 0 || n == 1 || n == 6 || n == 8) {
			cout << "pon" << endl;
			return 0;
		}
		else {
			cout << "bon" << endl;
			return 0;
		}
			

	}
	else if (10 <= n && n <= 99) {
		if (n%10 == 2 || n % 10 == 4 || n % 10 == 5 || n % 10 == 7 || n % 10 == 9) {
			cout << "hon" << endl;
			return 0;
		}
		else if (n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8) {
			cout << "pon" << endl;
			return 0;
		}
		else {
			cout << "bon" << endl;
			return 0;
		}

	}
	else if (100 <= n && n <= 999) {
		if (n % 10 == 2 || n % 10 == 4 || n % 10 == 5 || n  % 10 == 7 || n % 10 == 9) {
			cout << "hon" << endl;
			return 0;
		}
		else if (n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8) {
			cout << "pon" << endl;
			return 0;
		}
		else {
			cout << "bon" << endl;
			return 0;
		}

	}
	
}
	

Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void Alchemist()
{
  int n;
  cin >> n;
  vector<double>v(n);
  for (int i = 0; i < n; i++) cin >> v[i];
  sort(v.begin(), v.end());
  for (int i = 1; i < n; i++)
  {
    v[i] = (v[i - 1] + v[i]) / 2;
  }
  cout << v[n - 1] << endl;
  return;
}


int main()
{
  Alchemist();
  return 0;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long w, h, x, y;
  cin >> w >> h >> x >> y;
  long double s = w * h / 2.0;
  int t = (x * 2 == w && y * 2 == h) ? 1 : 0;
  cout << setprecision(13) << s << " " << t << '\n';
  return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
typedef complex<double> P;
typedef pair<P,P> L;
typedef pair<P,double> C;
typedef vector<P> Poly;
#define X real()
#define Y imag()
const double EPS = (1e-10), INF = (1e15), pi = acos(-1);

//2D version
double dot(P a, P b){ return a.X * b.X + a.Y * b.Y;}
double cross(P a, P b){ return a.X * b.Y - a.Y * b.X;}

int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if(cross(b,c) > EPS) return +1;
  if(cross(b,c) < -EPS) return -1;
  if(dot(b,c) < 0) return +2;
  if(abs(b) + EPS < abs(c)) return -2;
  return 0;
}

P projection(P a, P b){ return dot(a, b)/abs(b)/abs(b)*b;}

double ps_dist(P a, L s){
  if(dot(s.second-s.first,a-s.first) >= 0 && dot(s.first-s.second,a-s.second) >= 0)
    return abs(cross(s.first-s.second,a-s.second))/abs(s.first-s.second);
  return min(abs(a-s.first), abs(a-s.second));
}

double pl_dist(P a, L s){
  return abs(cross(s.first-s.second,a-s.second))/abs(s.first-s.second);
}

L cpcl(C c, L l){
  //円cと直線lの交点
  //接する場合は同一の点を二つ返す
  double d = pl_dist(c.first,l), r = c.second;
  P m = l.first + projection(c.first-l.first,l.second-l.first);
  P x = sqrt(r*r-d*d)/abs(l.second-l.first)*(l.second-l.first);
  if(dot(x,l.second-l.first) < 0) x *= -1;
  return make_pair(m-x,m+x);
}

double common_area_cp(C c, Poly p){
  //円と非凸多角形の共通面積
  double ret = 0, r = c.second;
  int n = p.size();
  for(int i = 0; i < n; ++i) p[i] -= c.first;
  for(int i = 0; i < n; ++i){
    if(abs(p[i]) < EPS || abs(p[(i+1)%n]) < EPS) continue;
    double d = arg(p[(i+1)%n]/p[i]);
    ret += r*r*d/2.0;
    if(ps_dist(P(0,0),L(p[i],p[(i+1)%n])) < r - EPS){
      L cps = cpcl(C(P(0,0),r),L(p[i],p[(i+1)%n]));
      P a, b;
      if(ccw(p[i],p[(i+1)%n],cps.first) == 0 &&
         ccw(p[i],p[(i+1)%n],cps.second) == 0)
        a = cps.first, b = cps.second;
      else if(ccw(p[i],p[(i+1)%n],cps.first) == 0)
        a = cps.first, b = p[(i+1)%n];
      else if(ccw(p[i],p[(i+1)%n],cps.second) == 0)
        a = p[i], b = cps.second;
      else
        a = p[i], b = p[(i+1)%n];
      if(abs(a) < EPS || abs(b) < EPS) continue;
      d = arg(b/a);
      ret += cross(a,b)/2.0 - r*r*d/2.0;
    }
  }
  //cout << r << " " << ret << endl;
  return ret;
}

int main(){
  int N, r;
  cin >> N >> r;
  Poly p;
  for(int i = 0; i < N; ++i){
    double x, y;
    cin >> x >> y;
    p.emplace_back(x,y);
  }
  double ans = 0;
  for(int i = 1; i <= r; ++i){
    if(i%2) ans += common_area_cp(C(P(0,0),i),p) - common_area_cp(C(P(0,0),i-1),p);
    else ans += (2*i-1)*pi - common_area_cp(C(P(0,0),i),p) + common_area_cp(C(P(0,0),i-1),p);
    //cout << common_area_cp(C(P(0,0),i),p) << endl;
  }
  printf("%.9f\n", ans);
  return 0;
}



Measured memory_bytes: 3548
R,G,B,N = map(int,input().split())
ans = 0
for i in range(0,N//R+1):
  for j in range(0,(N-i*R)//G+1):
    k = N - i*R -j*G
    if k%B == 0 and k>= 0:
      ans += 1
print(ans)


Measured memory_bytes: 9044
#include<iostream>
#include<cstdio>
#include<ctype.h>
using namespace std;
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch))f|=ch=='-',ch=getchar();
    while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
int a[1007][1007];
char c;
int main(){
	int n=read(),k=read(),ans=0;
	for(int i=0;i<n;++i){
		int x=read()%(k+k)+1,y=read()%(k+k)+1;cin>>c;
		int f=c=='B';
		if(x>k)x-=k,f^=1;
		if(y>k)y-=k,f^=1;
		if(f)a[1][1]++,a[x][1]--,a[1][y]--,a[x][y]+=2;
		else a[1][y]++,a[x][1]++,a[x][y]-=2;
	}
	for(int i=1;i<=k;++i)for(int j=1;j<=k;++j){
		a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
		ans=max(ans,max(n-a[i][j],a[i][j]));
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ldb;
typedef pair<ll,ll> pll;
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define V vector
#define endl "\n"
#define CLEAR(a) memset(a,0,sizeof(a))
#define all(x) x.begin(),x.end()
#define sz(x) ((ll)x.size())
#define rep0(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ios_tie() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(nullptr)
#define trace1(a)             cout <<#a<<":"<<a<< endl;
#define trace2(a,b)           cout <<#a<<":"<<a<<" | "<<#b<<":"<<b<< endl;
#define trace3(a,b,c)         cout <<#a<<":"<<a<<" | "<<#b<<":"<<b<<" | "<<#c<<":"<<c<<endl;
#define trace4(a,b,c,d)       cout <<#a<<":"<<a<<" | "<<#b<<":"<<b<<" | "<<#c<<":"<<c<<" | "<<#d<<":"<<d<<endl;

const ll inf = 1e18;
const ll mod = 1e9+7;
const ll maxn = 1e5+10;
const ldb PI = acos(-1);

void lol(ll s) {cerr<<"check........................................... "<<s<<endl;}
ll power(ll x,ll y) {ll res=1; x%=mod; while(y) {if(y&1) res=(res*x)%mod; y>>=1LL; x=(x*x)%mod; }return res;}
ll inv(ll x) {return power(x,mod-2);}//(1/x)%y = x^(y-2) % y;   // pow(x,y)%m = pow(x,y%(m-1))%m
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// I can solve mirror cube in 2 mins but can't solve div2 C in 1hr.
void solve()
{
    ll n, m, k;
    cin>>n>>m>>k;
    char mat[n+1][m+1];
    ll x1, y1, x2, y2;
    cin>>x1>>y1>>x2>>y2;
    ll mn[n+1][m+1];
    rep1(i,n) {
        rep1(j,m) {
            cin>>mat[i][j];
            mn[i][j] = inf;
        }
    }
    queue<pll> q;
    q.push({x1,y1});
    mn[x1][y1] = 0;
    ll dx[4] = {-1,1,0,0};
    ll dy[4] = {0,0,1,-1};
    while(!q.empty()) {
        ll i = q.front().ff;
        ll j = q.front().ss;
        q.pop();
        rep0(l,4) {
            for(ll a=1;a<=k;a++) {
                ll newj = j+a*dx[l];
                ll newi = i+a*dy[l];
                if(newi>=1 && newi<=n && newj>=1 && newj<=m && mat[newi][newj]=='.') {
                    if(mn[newi][newj]<mn[i][j]+1) {
                        break;
                    }
                    if(mn[newi][newj]!=inf) {
                        continue;
                    }
                    q.push({newi,newj});
                    mn[newi][newj] = mn[i][j]+1;
                }
                else {
                    break;
                }
            }

        }
    }
    if(mn[x2][y2]==inf)
        mn[x2][y2] = -1;
    cout<<mn[x2][y2]<<endl;
}
int main()
{
    ios_tie();
    // freopen("input.txt", "r", stdin);
    // freopen("myOut.txt", "w", stdout);
    ll _ = 1;
    // cin>>_;
    rep1(i,_)
    {
        // cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}


Measured memory_bytes: 14048
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		final int t = scan.nextInt();
		int totalTime = 0;

		Deque<String> queueName = new ArrayDeque<String>();
		Deque<Integer> queueTime = new ArrayDeque<Integer>();

		for(int i = 0; i < n; i++) {
			queueName.addLast(scan.next());
			queueTime.addLast(scan.nextInt());
		}

		while(!queueName.isEmpty()) {
			String procName = queueName.pollFirst();
			int procTime = queueTime.pollFirst();
			if(procTime <= t) {
				System.out.println(procName + " " + (procTime + totalTime));
				totalTime += procTime;
			} else {
				queueName.addLast(procName);
				queueTime.addLast(procTime - t);
				totalTime += t;
			}
		}
		scan.close();
	}
}


Measured memory_bytes: 74696
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+20;
const ll mod=1e9+7;
ll f[N],n,m,A,B;
ll powmod(ll x,ll n)
{
	ll s=1;
	while(n)
	{
		if(n&1)
			s=(s*x)%mod;
		x=(x*x)%mod;
		n>>=1;
	}
	return s;
}
ll C(ll n,ll m)
{
	ll a=f[n],b=(f[m]*f[n-m])%mod;
	return (a*powmod(b,mod-2))%mod;
}
int main()
{
	f[0]=1;
	for(ll i=1;i<N;i++)
		f[i]=(f[i-1]*i)%mod;
	while(cin>>n>>m>>A>>B)
	{
		ll res=0;
		for(ll i=B+1;i<=m;i++)
		{
			ll tmp=(C(i-1+n-A-1,n-A-1)*C(m-i+A-1,m-i))%mod;
			res=(res+tmp)%mod;
		}
		cout<<res<<endl;	
	}
	return 0;
}

Measured memory_bytes: 1792
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var x = cin.next()[0];
            var y = cin.next()[0];
            Console.WriteLine(x==y?"=":x<y?"<":">");
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public string[] ArrayString(int N)
        {
            string[] Array = new string[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = next();
            }
            return Array;
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#pragma optimize("O3")
#define array vector<vector<int>>
#define thread sort
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,a,b) for (int i = (a - 1); i >= (b); i--)
#define all(a) (a).begin(), (a).end()
#define endl "\n"
#define ll long long
#define pb push_back
#define PII pair<int, int>
#define PLL pair<long long, long long>
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define vll vector<long long>
#define mii map<int, int>
#define mll map<long long, long long>
#define MOD 1000000007
#define MAX 1000000007
#define MOD2 1234567891
#define MOD3 998244353
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



int main() {
    int n;
    cin >> n;
    vi v(n);
    int counter = 0;
    FOR (i, 0, n) {
        cin >> v[i];
        if (v[i] != i + 1)
            counter++;
    }
    if (counter > 2) {
        cout << "NO";
    } else {
        cout << "YES";
    }
    return 0;
}

Measured memory_bytes: 256
/*
          ,     \    /      ,
         / \    )\__/(     / \
        /   \  (_\  /_)   /   \
   ____/_____\__\@  @/___/_____\____
  |             |\../|              |
  |              \VV/               |
  |        ------hoi-------         |
  |_________________________________|
   |    /\ /      \\       \ /\    |
   |  /   V        ))       V   \  |
   |/     `       //        '     \|
   `              V                '
*/

#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define f first
#define se second
#define Speedforce boost();
#define fop(s1, s2) freopen(s1, "r", stdin);freopen(s2, "w", stdout);

using namespace std;

void boost(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

const int N = 1e6;
const ll inf = 1e9 + 7;
const ld PI = acos(-1);

ll bin_pow(ll x, ll y){
    ll res = 1, base = x;
    while(y){
        if(y & 1){
            res *= base;
            res %= inf;
        }
        base *= base;
        base %= inf;
        y /= 2;
    }
    return res;
}

string s;

int main(){
    Speedforce
    //fop("", "")
    cin >> s;
    if(s[2] == s[3] && s[4] == s[5]){
        cout << "Yes";
    }
    else{
        cout << "No";
    }
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		int q = sc.nextInt();
		for (int i = 0; i < q; i++) {
			int val = sc.nextInt();
			int res = Arrays.binarySearch(a, val);
			int tmp = res;
			while (res > 0 && res < n) {
				if (a[res - 1] == val) {
					--res;
				} else {
					break;
				}
			}
			if (res >= 0) {
				System.out.print(res + " ");
			} else {
				res *= -1;
				tmp *= -1;
				--tmp;
				--res;
				System.out.print(res + " ");
			}
			while (tmp >= 0 && tmp < n - 1) {
				if (a[tmp + 1] == val) {
					++tmp;
				} else {
					break;
				}
			}
			if (tmp >= 0 && tmp < n && a[tmp] == val) {
				++tmp;
			}
			System.out.println(tmp);
		}
		
	}
}



Measured memory_bytes: 132356
n,k=[int(i) for i in input().split()]
a_list=[int(s) for s in input().split()]

mod=10**9+7

# 単体の転倒数
first=0
for i in range(n-1):
    a=a_list[i]
    for j in range(i+1,n):
        if a>a_list[j]:
            first+=1

# 右に同じ列があったときの転倒数
rightnum=0            
for i in range(n):
    a=a_list[i]
    for a_all in a_list:
        if a>a_all:
            rightnum+=1

samecol=(k*(k-1)//2)%mod
ans=(samecol*rightnum)%mod
ans=(ans+first*k)%mod
print(ans)

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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

int main(void){
    for(int n, d; cin >> n >> d, n;){
        vvi c(n);
        vi sum(n);
        rep(i, n){
            int m; cin >> m;

            rep(j, m){
                int cc; cin >> cc;
                c[i].pb(cc);

                sum[i] += cc;
            }
        }

        bool ok = true;
        while(ok){
            ok = false;
            
            rep(i, n){
                while(c[i].size() != 0){
                    int cur_c = *(c[i].end() - 1);
                    sum[i] -= cur_c;
                    c[i].pop_back();

                    if(abs(*max_element(all(sum)) - sum[i]) > d){
                        sum[i] += cur_c;
                        c[i].pb(cur_c);
                        break;
                    }

                    ok = true;
                }
            }
        }

        if(*max_element(all(sum)) == 0) cout << "Yes" << endl;
        else                            cout << "No"  << endl;
    }

	return 0;
}

Measured memory_bytes: 1260
import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, VC):
    color = [WHITE for i in range(N)]
    d = [INFTY for i in range(N)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

N, M, S, T = map(int, input().split())
VA = [[] for i in range(N)]
VB = [[] for i in range(N)]
for i in range(M):
    u, v, a, b = list(map(int, input().split()))
    VA[u-1].append([v-1, a,])
    VA[v-1].append([u-1, a])
    VB[u-1].append([v-1, b])
    VB[v-1].append([u-1, b])

da = dijkstra(S-1, VA)
db = dijkstra(T-1, VB)
tmp = 10**16
base = 10 ** 15
ans = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    tmp = min(da[i] + db[i], tmp)
    ans[i] = tmp

for i in range(N):
    print(base - ans[i])


Measured memory_bytes: 124396
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int mod = 987654323;
const int ms = 100;
int a[ms], b[ms], c[ms];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    for (int i = 1; i < n; ++i) cin >> c[i];
    ll res = 0;
    for (int i = 1; i <= n; ++i)
    {
        res += b[a[i]];
        if (a[i - 1] == a[i] - 1)
        {
            res += c[a[i - 1]];
        }
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
  int n, h, max=0, ans=0;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> h;
    if(h >= max){
      max = h;
      ans++;
    }
  }
  cout << ans;
  return 0;
}

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

int N, M;
double L[20], A[20], B[20];

double distance(double l, double a, double b) {
  return l*l + a*a + b*b;
}

double calcDist(int S) {
  vector<int> v;
  for(int i = 0; i < N; ++i) 
    if(S & 1 << i) v.push_back(i);

  double res = 0;
  for(int i = 0; i < v.size(); ++i) {
    for(int j = i+1; j < v.size(); ++j) {
      res += distance(L[v[i]]-L[v[j]],A[v[i]]-A[v[j]],B[v[i]]-B[v[j]]);
    }
  }
  return res;
}

double solve() {
  double ans = 0;
  for(int S = 0; S < 1<<N; ++S) {
    int n = 0;
    for(int i = 0; i < N; ++i) if(S & 1<<i) ++n;
    if(n == M) ans = max(ans, calcDist(S));
  }
  return ans;
}

int main() {
  cin >> N >> M;
  for(int i = 0; i < N; ++i)
    cin >> L[i] >> A[i] >> B[i];
  printf("%.20f\n", solve());
  return 0;
}

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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)
 
typedef long long ll;
 
//const int INF = 1001001001;
const long long INF = 1e18;
const int MOD = 1000000007;
const double PI=acos(-1);


//-------------------------------------------------
struct edge{ll to, cost;};
typedef pair<ll,ll> P;
struct graph{
  ll V;
  vector<vector<edge> > G;
  vector<ll> d;

  graph(ll n){
    init(n);
  }

  void init(ll n){
    V = n;
    G.resize(V);
    d.resize(V);
    for(int i=0; i<V; i++){
      d[i] = INF;
    }
  }

  void add_edge(ll s, ll t, ll cost){
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }

  void dijkstra(ll s){
    for(int i=0; i<V; i++){
      d[i] = INF;
    }
    d[s] = 0;
    priority_queue<P,vector<P>, greater<P> > que; //first:dist from start, second:next v
    que.push(P(0,s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      ll v = p.second;
      if(d[v]<p.first) continue;
      for(auto e : G[v]){
        if(d[e.to]>d[v]+e.cost){
          d[e.to] = d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }
  }
};

int main() {
    int n,m,s,t;
    cin >> n >> m >> s >> t;
    s--,t--;
    graph g1(n), g2(n);

    rep(i,m) {
        int u,v,a,b;
        cin >> u >> v >> a >> b;
        u--,v--;
        g1.add_edge(u,v,a);
        g1.add_edge(v,u,a);
        g2.add_edge(u,v,b);
        g2.add_edge(v,u,b);
    }
    
    g1.dijkstra(s);
    g2.dijkstra(t);

    priority_queue<P, vector<P>> d;
    ll total = 1000000000000000;
    rep(i,n) {
        d.push(P(total-(g1.d[i] + g2.d[i]),i));
    }

    rep(i,n) {
        while (d.top().second<i) {
            d.pop();
        }
        auto ans = d.top();
        cout << ans.first << endl;
    }


}

Measured memory_bytes: 19836
import itertools

def calc(A_list):
    ans = 0
    for A in A_list:
        score = 0     
        for i in range(Q):
            a, b, c, d = X[i]
            if A[b-1] -A[a-1] == c:
                score += d
        ans = max(ans, score)
    return ans

N, M, Q = map(int, input().split())
X = [[0]*4 for _ in range(Q)]

for i in range(Q):
    X[i] = list(map(int, input().split()))

l = [i for i in range(1, M+1)]
A_list = list(itertools.combinations_with_replacement(l, N))
print(calc(A_list))


Measured memory_bytes: 87432
#include<bits/stdc++.h>
 
using namespace std;
 
#define INF 1000000007
#define LINF 1000000000000000007
 
typedef long long i64;
typedef pair<i64,i64> P;


int a,b;

int main(){
	cin >> a >> b;
	
	if(b%a) cout << b-a << endl;
	else cout << a + b << endl;
	
	return 0;;
}

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

int main(){
  int N; 
  string S = "";
  cin >> N >> S;
int count =0;
int fin = 0;
 for(int i=0; i<N; ++i){
    if(S[i]=='I'){
      count ++;}
    else if(S[i] == 'D'){
      count --;}
    fin= max(fin, count);
  }
   cout << fin << endl; 
   
  
}

Measured memory_bytes: 256