oj.uz

Submission #23073

# Submission time Handle Problem Language Result Execution time Memory
23073 2017-05-02T15:29:56 Z model_code Kvalitetni (COCI16_kvalitetni) C++11
120 / 120
 16 ms 42724 KB 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const int MAXN = 1000010;

enum {ADD, MUL};

char a[MAXN];
stack<int> s;
vector<int> e[MAXN];
int n, m, k, z[MAXN], op[MAXN];
double val[MAXN];

bool cmp(int i, int j) {
  return val[i] < val[j];
}

double get_mul(vector<int>& v) {
  assert((int)v.size() <= k);
  sort(v.begin(), v.end(), cmp);
  double tot = z[(int)v.size()];
  
  double ret = 1;
  for (int i = 0; i < (int)v.size(); ++i) {
    int rem = (int)v.size() - i;
    if (tot / rem < val[v[i]]) {
      for (int j = i; j < (int)v.size(); ++j)
	ret *= tot / rem;
      break;
    } else {
      ret *= val[v[i]];
      tot -= val[v[i]];
    }
  }
  return ret;
}

double get_add(vector<int>& v) {
  double ret = 0;
  for (int i = 0; i < (int)v.size(); ++i)
    ret += val[v[i]];
  return min(ret, (double)z[(int)v.size()]);
}

int main(void) {
  scanf("%d",&k);
  for (int i = 1; i <= k; ++i)
    scanf("%d",&z[i]);
  scanf("%s",a);
  n = strlen(a);

  for (int i = 0; i < n; ++i) {
    if (a[i] == '(') {
      if (!s.empty()) {
	e[s.top()].push_back(m);
      }
      s.push(m++);
    }
    else if (a[i] == '+')
      op[s.top()] = ADD;
    else if (a[i] == '*')
      op[s.top()] = MUL;
    else if (a[i] == ')') {
      int x = s.top();
      s.pop();
      if (e[x].empty()) {
	val[x] = z[1];
	assert(val[x] != 0);
      }
      else {
	val[x] = (op[x] == ADD) ? get_add(e[x]) : get_mul(e[x]);
      }
    }
  }

  printf("%.9lf\n",val[0] + 1e-3 + 1e-4);

  return 0;
}

Compilation message

kvalitetni.cpp: In function 'int main()':
kvalitetni.cpp:53:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&k);
                 ^
kvalitetni.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&z[i]);
                      ^
kvalitetni.cpp:56:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",a);
                ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 42064 KB Output is correct
2 Correct 9 ms 42064 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 42064 KB Output is correct
2 Correct 6 ms 42064 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 42064 KB Output is correct
2 Correct 3 ms 42064 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42064 KB Output is correct
2 Correct 9 ms 42064 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42064 KB Output is correct
2 Correct 9 ms 42064 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 42064 KB Output is correct
2 Correct 9 ms 42196 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 42064 KB Output is correct
2 Correct 9 ms 42460 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 42196 KB Output is correct
2 Correct 13 ms 42460 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 42328 KB Output is correct
2 Correct 16 ms 42724 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 42328 KB Output is correct
2 Correct 9 ms 42592 KB Output is correct